Simplify ConvexPolyhedron creation #103
Labels
enhancement
New feature or request
Comments
|
I'm experiencing this exact problem too. Anybody have an idea of a fix? |
|
Hi there, could you post this example as a codesandbox? And if you know how to get this information, the length of your index arrays in each shape? |
stockhuman
added
the
awaiting author feedback
Out of curiosity, did you also try deleting the uv coordinates? Because after a small amount of experimentation, if you don't delete the uv mapping on the tetrahedron geometry, none of the vertices get merged. So, if you have your heart set on having the uv mapping there, I think you can clone the geometry, delete all the attributes but the position, merge the vertices, and use that for making the shape. That might work, but I haven't tested it. And, the Buffer Geometry Utils was working for you, right? Because Cannon es is a type script engine, so I wasn't sure how well those mesh. I am a primarily javascript developer, because I can't download typescript, at least, not yet anyway, so I am sorely inexperienced in that area. But, try cloning the geometry, and only keeping the position attribute, merging the vertices, and using the new geometry to make the shape rather than the old one. Might be a bit innefficient, but cant really think of any other way to keep the uv mapping. Edit: function createFromIndexed(mesh){
let geometry = new THREE.BufferGeometry();
geometry.setAttribute('position', mesh.geometry.getAttribute('position'));
geometry = THREE.BufferGeometryUtils.mergeVertices(geometry);
//if using import statement
//geometry = BufferGeometryUtils.mergeVertices(geometry);
let position = geometry.attributes.position.array;
let geomFaces = geometry.index.array;
const points = [];
const faces = [];
for(var i = 0; i < position.length; i += 3){
points.push(new CANNON.Vec3(position[i], position[i+1], position[i+2]);
}
for(var i = 0; i < geomFaces.length; i += 3){
faces.push([geomFaces[i], geomFaces[i+1], geomFaces[i+2]);
}
return new CANNON.ConvexPolyhedron(points,faces);
}And that should work. This is written in javascript, so you would have to convert it to typescript, but other than that, it should work, because all vertices in the geometry are merged, so you get a solid convex representation, and you don't lose any data from the original geometry, so, you keep the uv and normals, but should still get convex-convex collision |
|
This is an error that happens while converting a three.js geometry to a Closing this, feel free to reopen it if you provide an example. |
|
Found the repro example in schteppe#459, so I fixed it, here it is working: https://codesandbox.io/s/old-resonance-xpsn1?file=/src/index.js The conversion function looks like this: function getPolyhedronShape(mesh) {
let geometry = new THREE.BufferGeometry();
geometry.setAttribute("position", mesh.geometry.getAttribute("position"));
geometry = mergeVertices(geometry);
const position = geometry.attributes.position.array;
const index = geometry.index.array;
const points = [];
for (let i = 0; i < position.length; i += 3) {
points.push(new CANNON.Vec3(position[i], position[i + 1], position[i + 2]));
}
const faces = [];
for (let i = 0; i < index.length; i += 3) {
faces.push([index[i], index[i + 1], index[i + 2]]);
}
return new CANNON.ConvexPolyhedron({ vertices: points, faces });
} |
marcofugaro
changed the title
|
There should be a simpler way to do this.. reopening this issue until I figure it out |
|
Why don't you do what Ammo.js does and automatically create the convex hull given a set of points, rather than having the person put in an array of points and faces, and then checking whether that is convex? |
|
Yeah that should be easier, I'll look into the quickhull algorithm |
|
if it helps, i do have a file that has everything you need for the quickhull algorithm in it, including a way of getting the convex hull faces from a set of points |
|
Yess, please share what you have, it would be really useful 🙏 |
|
Apparently it doesn't support .js files, so I had to zip it, but here it is. As I said above, I am mainly a JS developer because I cant download the tools for TS, so that is what the file is written in, so I hope that isn't too much of an inconvenience. But, I have used this multiple times, and it works, and there is also a convenience static method in it for automatically creating the hull, and returning the faces. Cheers. Edit: |
marcofugaro
added
enhancement
|
One way I can think of simplifying the creation would to just add a static property to the convex polyhedron shape. i.e. //imported the ConvexPolyhedron and QuickHull file that I put above
//points is an array of CANNON.Vec3 so that way we can plug it straight into the CANNON.ConvexPolyhedron
ConvexPolyhedron.createHullFromPoints = function(points){
const faces = QuickHull.createHull(points);
return new ConvexPolyhedron({vertices:points, faces});
}and it should be that simple to make. Edit: |
|
I've been trying to work on something like this for some time. Even when using ConvexGeometry from Three.js, I get errors along the lines of This in an incredibly frustrating part of the library. Would love to see some development here. |
|
Thanks for sharing the QuickHull implementation, @Dannie226! Was a huge help. I'm working on a way easily convert complex geometries into decomposed convex shapes in browser/Node.js, such that they can collide with other shapes, not just spheres: https://twitter.com/GlavinW/status/1518397865592303618?s=20&t=db0kTGnYxorVMd-_93CqjQ With the QuickHull implementation above and using
For those interested below are a couple lessons learned with code. Convert Mesh's geometry to vertices and facesUnfortunately, I was unable to get #103 (comment) to work. If I recall correctly, Looking at - geometry.index.array;
+ geometry.getIndex();As a temporary solution, I created a hacky workaround using // object being an instance of https://threejs.org/docs/?q=object3#api/en/core/Object3D
function getVerticesAndFaces(object) {
return useMemo(() => {
const exporter = new OBJExporter();
const contents = exporter.parse(object);
const rows = contents
.split("\n")
.filter(Boolean)
.map((line) => line.split(" "));
const vertices = rows
.filter((row) => row[0] === "v")
.map((row) => row.slice(1).map(parseFloat));
const faces = rows
.filter((row) => row[0] === "f")
.map((row) => row.slice(1))
.map((row) => row.map((cell) => parseInt(cell.split("/")[0], 10) - 1));
return {
vertices,
faces,
};
}, [object]);
}Convert hulls (groups of vertices) to ConvexPolyhedronsThis might not be relevant to everyone. I want to show how groups of vertices (in my case convex hulls, function useHullShapes({ hulls }) {
const shapes = useMemo(() => {
if (!hulls) {
return null;
}
return hulls.map((shapePoints) => {
const vertices = shapePoints.map((p) => new THREE.Vector3().fromArray(p));
const faces = QuickHull.createHull(vertices);
return {
type: "ConvexPolyhedron",
position: [0, 0, 0],
rotation: [0, 0, 0],
args: [shapePoints, faces],
};
});
}, [hulls]);
return shapes;
}And now to const shapes = useHullShapes({ hulls });
const [ref] = useCompoundBody(
() => ({
// ...
shapes,
}),
undefined,
[shapes, ...]
);I got most of the way there thanks for this thread so wanted to contribute back what I learned. Hope this helps others, too! |
|
Glad that my implementation worked and was helpful |
|
@Glavin001, one thing to note though. For ease of use purposes, the code that I wrote can take in a 2D array of numbers, or an array of 3D vectors (just objects with an x, y, and z component). The code to convert to the THREE.Vector3 array is not necessary, and the vectors just get converted back to a 2D array of numbers. I am assuming that shapePoints is a 2D array of numbers? If so, just pass shape points into the function for creating the hull, and the rest is done for you. |
|
I just converted QuickHull to TypeScript. QuickHull.ts (expand)export const dot = (a: number[], b: number[]) => {
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
};
export const pointLineDistance = (p: number[], l1: number[], l2: number[]) => {
//https://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
const x10 = new Array(3);
const x21 = new Array(3);
const c = new Array(3);
subtract(x10, l1, p);
subtract(x21, l2, l1);
cross(c, x21, x10);
const len = length(c) / length(x21);
if (isNaN(len)) return 0;
return len;
};
export const getPlaneNormal = (
t: number[],
a: number[],
b: number[],
c: number[]
) => {
const v1 = new Array(3);
const v2 = new Array(3);
subtract(v1, b, a);
subtract(v2, b, c);
cross(t, v2, v1);
return t;
};
export const add = (t: number[], v1: number[], v2: number[]) => {
t[0] = v1[0] + v2[0];
t[1] = v1[1] + v2[1];
t[2] = v1[2] + v2[2];
return t;
};
export const subtract = (t: number[], v1: number[], v2: number[]) => {
t[0] = v1[0] - v2[0];
t[1] = v1[1] - v2[1];
t[2] = v1[2] - v2[2];
return t;
};
export const cross = (t: number[], v1: number[], v2: number[]) => {
t[0] = v1[1] * v2[2] - v1[2] * v2[1];
t[1] = v1[2] * v2[0] - v1[0] * v2[2];
t[2] = v1[0] * v2[1] - v1[1] * v2[0];
return t;
};
export const copy = (t: number[], f: number[]) => {
t[0] = f[0];
t[1] = f[1];
t[2] = f[2];
return t;
};
export const length = (v: number[]) => {
return Math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
};
export const scale = (t: number[], v: number[], l: number) => {
t[0] = v[0] * l;
t[1] = v[1] * l;
t[2] = v[2] * l;
return t;
};
export const scaleAndAdd = (
t: number[],
v1: number[],
l: number,
s: number
) => {
t[0] = v1[0] * l + s;
t[1] = v1[1] * l + s;
t[2] = v1[2] * l + s;
return t;
};
export const normalize = (t: number[], v: number[]) => {
let len = length(v);
if (len === 0) {
t[0] = 0;
t[1] = 0;
t[2] = 0;
} else {
len = 1 / len;
t[0] = v[0] * len;
t[1] = v[1] * len;
t[2] = v[2] * len;
}
return t;
};
export const distance = (v1: number[], v2: number[]) => {
return Math.sqrt(squaredDistance(v1, v2));
};
export const squaredDistance = (v1: number[], v2: number[]) => {
return (v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2 + (v1[2] - v2[2]) ** 2;
};
export const debug = (...text: any) => {
if (debug.enabled) console.log(...text);
};
debug.enabled = false;
export class VertexList {
public head: Vertex | null;
public tail: Vertex | null;
constructor() {
this.head = null;
this.tail = null;
}
clear() {
this.head = this.tail = null;
}
/**
* Inserts a `node` before `target`, it's assumed that
* `target` belongs to this doubly linked list
*
* @param {*} target
* @param {*} node
*/
insertBefore(target: Vertex, node: Vertex) {
node.prev = target.prev;
node.next = target;
if (!node.prev) {
this.head = node;
} else {
node.prev.next = node;
}
target.prev = node;
}
/**
* Inserts a `node` after `target`, it's assumed that
* `target` belongs to this doubly linked list
*
* @param {Vertex} target
* @param {Vertex} node
*/
insertAfter(target: Vertex, node: Vertex) {
node.prev = target;
node.next = target.next;
if (!node.next) {
this.tail = node;
} else {
node.next.prev = node;
}
target.next = node;
}
/**
* Appends a `node` to the end of this doubly linked list
* Note: `node.next` will be unlinked from `node`
* Note: if `node` is part of another linked list call `addAll` instead
*
* @param {*} node
*/
add(node: Vertex) {
if (!this.head) {
this.head = node;
} else {
if (!this.tail) throw new Error("tail is null");
this.tail.next = node;
}
node.prev = this.tail;
// since node is the new end it doesn't have a next node
node.next = null;
this.tail = node;
}
/**
* Appends a chain of nodes where `node` is the head,
* the difference with `add` is that it correctly sets the position
* of the node list `tail` property
*
* @param {*} node
*/
addAll(node: Vertex) {
if (!this.head) {
this.head = node;
} else {
if (!this.tail) throw new Error("tail is null");
this.tail.next = node;
}
node.prev = this.tail;
// find the end of the list
while (node.next) {
node = node.next;
}
this.tail = node;
}
/**
* Deletes a `node` from this linked list, it's assumed that `node` is a
* member of this linked list
*
* @param {*} node
*/
remove(node: Vertex) {
if (!node.prev) {
this.head = node.next;
} else {
node.prev.next = node.next;
}
if (!node.next) {
this.tail = node.prev;
} else {
node.next.prev = node.prev;
}
}
/**
* Removes a chain of nodes whose head is `a` and whose tail is `b`,
* it's assumed that `a` and `b` belong to this list and also that `a`
* comes before `b` in the linked list
*
* @param {*} a
* @param {*} b
*/
removeChain(a: Vertex, b: Vertex) {
if (!a.prev) {
this.head = b.next;
} else {
a.prev.next = b.next;
}
if (!b.next) {
this.tail = a.prev;
} else {
b.next.prev = a.prev;
}
}
first() {
return this.head;
}
isEmpty() {
return !this.head;
}
}
export class Vertex {
public point: number[];
public index: number;
public next: Vertex | null;
public prev: Vertex | null;
public face: Face | null;
constructor(point: number[], index: number) {
this.point = point;
// index in the input array
this.index = index;
// vertex is a double linked list node
this.next = null;
this.prev = null;
// the face that is able to see this point
this.face = null;
}
}
export class HalfEdge {
public vertex: Vertex;
public next: HalfEdge | null;
public prev: HalfEdge | null;
public face: Face | null;
public opposite: HalfEdge | null;
constructor(vertex: Vertex, face: Face) {
this.vertex = vertex;
this.face = face;
this.next = null;
this.prev = null;
this.opposite = null;
}
head() {
return this.vertex;
}
tail() {
return this.prev ? this.prev.vertex : null;
}
length() {
if (this.tail()) {
return distance(this.tail()?.point || [0, 0], this.head().point);
}
return -1;
}
lengthSquared() {
if (this.tail()) {
return squaredDistance(
this.tail()?.point || [0, 0],
this.head().point
);
}
return -1;
}
setOpposite(edge: HalfEdge) {
// eslint-disable-next-line @typescript-eslint/no-this-alias
const me = this;
if (debug.enabled) {
debug(
`opposite ${me.tail()?.index} <--> ${
me.head()?.index
} between ${me.face?.collectIndices()}, ${edge.face?.collectIndices()}`
);
}
this.opposite = edge;
edge.opposite = this;
}
}
const VISIBLE = 0;
const NON_CONVEX = 1;
const DELETED = 2;
export class Face {
public normal: number[];
public centroid: number[];
public offset: number;
public outside: Vertex | null;
public mark: number;
public edge: HalfEdge | null;
public nVertices: number;
public area = 0;
constructor() {
this.normal = [];
this.centroid = [];
// signed distance from face to the origin
this.offset = 0;
// pointer to the a vertex in a double linked list this face can see
this.outside = null;
this.mark = VISIBLE;
this.edge = null;
this.nVertices = 0;
}
getEdge(i: number) {
if (typeof i !== "number") {
throw Error("requires a number");
}
let it = this.edge;
while (i > 0) {
it = it?.next || it;
i -= 1;
}
while (i < 0) {
it = it?.prev || it;
i += 1;
}
return it;
}
computeNormal() {
const e0 = this.edge;
const e1 = e0?.next;
let e2 = e1?.next;
const v2 = subtract(
[],
e1?.head().point || [0, 0],
e0?.head().point || [0, 0]
);
const t: number[] = [];
const v1: number[] = [];
this.nVertices = 2;
this.normal = [0, 0, 0];
while (e2 !== e0) {
copy(v1, v2);
subtract(
v2,
e2?.head().point || [0, 0],
e0?.head().point || [0, 0]
);
add(this.normal, this.normal, cross(t, v1, v2));
e2 = e2?.next;
this.nVertices += 1;
}
this.area = length(this.normal);
// normalize the vector, since we've already calculated the area
// it's cheaper to scale the vector using this quantity instead of
// doing the same operation again
this.normal = scale(this.normal, this.normal, 1 / this.area);
}
computeNormalMinArea(minArea: number) {
this.computeNormal();
if (this.area < minArea) {
// compute the normal without the longest edge
let maxEdge;
let maxSquaredLength = 0;
let edge = this.edge || null;
// find the longest edge (in length) in the chain of edges
do {
const lengthSquared = edge?.lengthSquared() || 0;
if (lengthSquared > maxSquaredLength) {
maxEdge = edge;
maxSquaredLength = lengthSquared;
}
edge = edge?.next || null;
} while (edge !== this.edge);
const p1 = maxEdge?.tail()?.point;
const p2 = maxEdge?.head().point;
const maxVector = subtract([], p2 || [0, 0], p1 || [0, 0]);
const maxLength = Math.sqrt(maxSquaredLength);
// maxVector is normalized after this operation
scale(maxVector, maxVector, 1 / maxLength);
// compute the projection of maxVector over this face normal
const maxProjection = dot(this.normal, maxVector);
// subtract the quantity maxEdge adds on the normal
scaleAndAdd(
this.normal,
this.normal,
maxVector.length,
-maxProjection
);
// renormalize `this.normal`
normalize(this.normal, this.normal);
}
}
computeCentroid() {
this.centroid = [0, 0, 0];
let edge = this.edge;
do {
add(this.centroid, this.centroid, edge?.head().point || [0, 0]);
edge = edge?.next || null;
} while (edge !== this.edge);
scale(this.centroid, this.centroid, 1 / this.nVertices);
}
computeNormalAndCentroid(minArea?: number) {
if (typeof minArea !== "undefined") {
this.computeNormalMinArea(minArea);
} else {
this.computeNormal();
}
this.computeCentroid();
this.offset = dot(this.normal, this.centroid);
}
distanceToPlane(point: number[]) {
return dot(this.normal, point) - this.offset;
}
/**
* @private
*
* Connects two edges assuming that prev.head().point === next.tail().point
*
* @param {HalfEdge} prev
* @param {HalfEdge} next
*/
private connectHalfEdges(prev: HalfEdge, next: HalfEdge) {
let discardedFace;
if (prev.opposite?.face === next.opposite?.face) {
// `prev` is remove a redundant edge
const oppositeFace = next.opposite?.face || null;
let oppositeEdge;
if (prev === this.edge) {
this.edge = next;
}
if (oppositeFace?.nVertices === 3) {
// case:
// remove the face on the right
//
// /|\
// / | \ the face on the right
// / | \ --> opposite edge
// / a | \
// *----*----*
// / b | \
// ▾
// redundant edge
//
// Note: the opposite edge is actually in the face to the right
// of the face to be destroyed
oppositeEdge = next.opposite?.prev?.opposite;
oppositeFace.mark = DELETED;
discardedFace = oppositeFace;
} else {
// case:
// t
// *----
// /| <- right face's redundant edge
// / | opposite edge
// / | ▴ /
// / a | | /
// *----*----*
// / b | \
// ▾
// redundant edge
oppositeEdge = next.opposite?.next;
// make sure that the link `oppositeFace.edge` points correctly even
// after the right face redundant edge is removed
if (oppositeFace?.edge === oppositeEdge?.prev) {
if (!oppositeFace) throw Error("oppositeFace is null!");
oppositeFace.edge = oppositeEdge || null;
}
// /| /
// / | t/opposite edge
// / | / ▴ /
// / a |/ | /
// *----*----*
// / b \
if (!oppositeEdge) throw Error("oppositeEdge is null!");
oppositeEdge.prev = oppositeEdge?.prev?.prev || null;
if (!oppositeEdge.prev)
throw Error("oppositeEdge.prev is null!");
oppositeEdge.prev.next = oppositeEdge || null;
}
// /|
// / |
// / |
// / a |
// *----*----*
// / b ▴ \
// |
// redundant edge
next.prev = prev.prev;
if (!next.prev) throw Error("next.prev is null!");
next.prev.next = next;
// / \ \
// / \->\
// / \<-\ opposite edge
// / a \ \
// *----*----*
// / b ^ \
if (!oppositeEdge) throw Error("oppositeEdge is null!");
next.setOpposite(oppositeEdge);
oppositeFace?.computeNormalAndCentroid();
} else {
// trivial case
// *
// /|\
// / | \
// / |--> next
// / a | \
// *----*----*
// \ b | /
// \ |--> prev
// \ | /
// \|/
// *
prev.next = next;
next.prev = prev;
}
return discardedFace;
}
mergeAdjacentFaces(
adjacentEdge: HalfEdge,
discardedFaces: (Face | null)[] = []
) {
const oppositeEdge = adjacentEdge.opposite;
const oppositeFace = oppositeEdge?.face || null;
discardedFaces.push(oppositeFace || null);
if (!oppositeFace) throw Error("oppositeFace is null!");
oppositeFace.mark = DELETED;
// find the chain of edges whose opposite face is `oppositeFace`
//
// ===>
// \ face /
// * ---- * ---- * ---- *
// / opposite face \
// <===
//
let adjacentEdgePrev = adjacentEdge.prev;
let adjacentEdgeNext = adjacentEdge.next;
let oppositeEdgePrev = oppositeEdge?.prev;
let oppositeEdgeNext = oppositeEdge?.next;
// left edge
while (adjacentEdgePrev?.opposite?.face === oppositeFace) {
adjacentEdgePrev = adjacentEdgePrev.prev;
oppositeEdgeNext = oppositeEdgeNext?.next;
}
// right edge
while (adjacentEdgeNext?.opposite?.face === oppositeFace) {
adjacentEdgeNext = adjacentEdgeNext.next;
oppositeEdgePrev = oppositeEdgePrev?.prev;
}
// adjacentEdgePrev \ face / adjacentEdgeNext
// * ---- * ---- * ---- *
// oppositeEdgeNext / opposite face \ oppositeEdgePrev
// fix the face reference of all the opposite edges that are not part of
// the edges whose opposite face is not `face` i.e. all the edges that
// `face` and `oppositeFace` do not have in common
let edge;
for (
edge = oppositeEdgeNext;
edge !== oppositeEdgePrev?.next;
edge = edge?.next
) {
if (!edge) throw Error("edge is null!");
edge.face = this;
}
// make sure that `face.edge` is not one of the edges to be destroyed
// Note: it's important for it to be a `next` edge since `prev` edges
// might be destroyed on `connectHalfEdges`
this.edge = adjacentEdgeNext;
// connect the extremes
// Note: it might be possible that after connecting the edges a triangular
// face might be redundant
let discardedFace;
if (!oppositeEdgePrev) throw Error("adjacentEdgePrev is null!");
if (!adjacentEdgeNext) throw Error("adjacentEdgeNext is null!");
if (!adjacentEdgePrev) throw Error("adjacentEdgePrev is null!");
if (!oppositeEdgeNext) throw Error("oppositeEdgeNext is null!");
discardedFace = this.connectHalfEdges(
oppositeEdgePrev,
adjacentEdgeNext
);
if (discardedFace) {
discardedFaces.push(discardedFace);
}
discardedFace = this.connectHalfEdges(
adjacentEdgePrev,
oppositeEdgeNext
);
if (discardedFace) {
discardedFaces.push(discardedFace);
}
this.computeNormalAndCentroid();
// TODO: additional consistency checks
return discardedFaces;
}
collectIndices() {
const indices = [];
let edge = this.edge;
do {
indices.push(edge?.head().index);
edge = edge?.next || null;
} while (edge !== this.edge);
return indices;
}
static createTriangle(v0: Vertex, v1: Vertex, v2: Vertex, minArea = 0) {
const face = new Face();
const e0 = new HalfEdge(v0, face);
const e1 = new HalfEdge(v1, face);
const e2 = new HalfEdge(v2, face);
// join edges
e0.next = e2.prev = e1;
e1.next = e0.prev = e2;
e2.next = e1.prev = e0;
// main half edge reference
face.edge = e0;
face.computeNormalAndCentroid(minArea);
if (debug.enabled) {
debug("face created %j", face?.collectIndices());
}
return face;
}
}
const MERGE_NON_CONVEX_WRT_LARGER_FACE = 1;
const MERGE_NON_CONVEX = 2;
export class QuickHull {
public tolerance: number;
public nFaces: number;
public nPoints: number;
public faces: Face[];
public newFaces: Face[];
public claimed: VertexList;
public unclaimed: VertexList;
public vertices: Vertex[];
public discardedFaces: Face[];
public vertexPointIndices: number[];
constructor(points: number[][]) {
if (!Array.isArray(points)) {
throw TypeError("input is not a valid array");
}
if (points.length < 4) {
throw Error("cannot build a simplex out of <4 points");
}
this.tolerance = -1;
// buffers
this.nFaces = 0;
this.nPoints = points.length;
this.faces = [];
this.newFaces = [];
// helpers
//
// let `a`, `b` be `Face` instances
// let `v` be points wrapped as instance of `Vertex`
//
// [v, v, ..., v, v, v, ...]
// ^ ^
// | |
// a.outside b.outside
//
this.claimed = new VertexList();
this.unclaimed = new VertexList();
// vertices of the hull(internal representation of points)
this.vertices = [];
for (let i = 0; i < points.length; i += 1) {
this.vertices.push(new Vertex(points[i], i));
}
this.discardedFaces = [];
this.vertexPointIndices = [];
}
addVertexToFace(vertex: Vertex, face: Face) {
vertex.face = face;
if (!face.outside) {
this.claimed.add(vertex);
} else {
this.claimed.insertBefore(face.outside, vertex);
}
face.outside = vertex;
}
/**
* Removes `vertex` for the `claimed` list of vertices, it also makes sure
* that the link from `face` to the first vertex it sees in `claimed` is
* linked correctly after the removal
*
* @param {Vertex} vertex
* @param {Face} face
*/
removeVertexFromFace(vertex: Vertex, face: Face) {
if (vertex === face.outside) {
// fix face.outside link
if (vertex.next && vertex.next.face === face) {
// face has at least 2 outside vertices, move the `outside` reference
face.outside = vertex.next;
} else {
// vertex was the only outside vertex that face had
face.outside = null;
}
}
this.claimed.remove(vertex);
}
/**
* Removes all the visible vertices that `face` is able to see which are
* stored in the `claimed` vertext list
*
* @param {Face} face
* @return {Vertex|undefined} If face had visible vertices returns
* `face.outside`, otherwise undefined
*/
removeAllVerticesFromFace(face: Face) {
if (face.outside) {
// pointer to the last vertex of this face
// [..., outside, ..., end, outside, ...]
// | | |
// a a b
let end = face.outside;
while (end.next && end.next.face === face) {
end = end.next;
}
this.claimed.removeChain(face.outside, end);
// b
// [ outside, ...]
// | removes this link
// [ outside, ..., end ] -┘
// | |
// a a
end.next = null;
return face.outside;
}
}
/**
* Removes all the visible vertices that `face` is able to see, additionally
* checking the following:
*
* If `absorbingFace` doesn't exist then all the removed vertices will be
* added to the `unclaimed` vertex list
*
* If `absorbingFace` exists then this method will assign all the vertices of
* `face` that can see `absorbingFace`, if a vertex cannot see `absorbingFace`
* it's added to the `unclaimed` vertex list
*
* @param {Face} face
* @param {Face} [absorbingFace]
*/
deleteFaceVertices(face: Face, absorbingFace: Face) {
const faceVertices = this.removeAllVerticesFromFace(face);
if (faceVertices) {
if (!absorbingFace) {
// mark the vertices to be reassigned to some other face
this.unclaimed.addAll(faceVertices);
} else {
// if there's an absorbing face try to assign as many vertices
// as possible to it
// the reference `vertex.next` might be destroyed on
// `this.addVertexToFace` (see VertexList#add), nextVertex is a
// reference to it
let nextVertex;
for (
let vertex: Vertex | null = faceVertices;
vertex;
vertex = nextVertex
) {
nextVertex = vertex.next;
const distance = absorbingFace.distanceToPlane(
vertex.point
);
// check if `vertex` is able to see `absorbingFace`
if (distance > this.tolerance) {
this.addVertexToFace(vertex, absorbingFace);
} else {
this.unclaimed.add(vertex);
}
}
}
}
}
/**
* Reassigns as many vertices as possible from the unclaimed list to the new
* faces
*
* @param {Faces[]} newFaces
*/
resolveUnclaimedPoints(newFaces: Face[]) {
// cache next vertex so that if `vertex.next` is destroyed it's still
// recoverable
let vertexNext = this.unclaimed.first();
for (let vertex = vertexNext; vertex; vertex = vertexNext) {
vertexNext = vertex.next;
let maxDistance = this.tolerance;
let maxFace;
for (let i = 0; i < newFaces.length; i += 1) {
const face = newFaces[i];
if (face.mark === VISIBLE) {
const dist = face.distanceToPlane(vertex.point);
if (dist > maxDistance) {
maxDistance = dist;
maxFace = face;
}
if (maxDistance > 1000 * this.tolerance) {
break;
}
}
}
if (maxFace) {
this.addVertexToFace(vertex, maxFace);
}
}
}
/**
* Computes the extremes of a tetrahedron which will be the initial hull
*
* @return {number[]} The min/max vertices in the x,y,z directions
*/
computeExtremes() {
// eslint-disable-next-line @typescript-eslint/no-this-alias
const me = this;
const min = [];
const max = [];
// min vertex on the x,y,z directions
const minVertices = [];
// max vertex on the x,y,z directions
const maxVertices = [];
let i, j;
// initially assume that the first vertex is the min/max
for (i = 0; i < 3; i += 1) {
minVertices[i] = maxVertices[i] = this.vertices[0];
}
// copy the coordinates of the first vertex to min/max
for (i = 0; i < 3; i += 1) {
min[i] = max[i] = this.vertices[0].point[i];
}
// compute the min/max vertex on all 6 directions
for (i = 0; i < this.vertices.length; i += 1) {
const vertex = this.vertices[i];
const point = vertex.point;
// update the min coordinates
for (j = 0; j < 3; j += 1) {
if (point[j] < min[j]) {
min[j] = point[j];
minVertices[j] = vertex;
}
}
// update the max coordinates
for (j = 0; j < 3; j += 1) {
if (point[j] > max[j]) {
max[j] = point[j];
maxVertices[j] = vertex;
}
}
}
// compute epsilon
this.tolerance =
3 *
Number.EPSILON *
(Math.max(Math.abs(min[0]), Math.abs(max[0])) +
Math.max(Math.abs(min[1]), Math.abs(max[1])) +
Math.max(Math.abs(min[2]), Math.abs(max[2])));
if (debug.enabled) {
debug("tolerance %d", me.tolerance);
}
return [minVertices, maxVertices];
}
/**
* Compues the initial tetrahedron assigning to its faces all the points that
* are candidates to form part of the hull
*/
createInitialSimplex() {
const vertices = this.vertices;
const [min, max] = this.computeExtremes();
let v0, v1, v2, v3;
let i, j;
// Find the two vertices with the greatest 1d separation
// (max.x - min.x)
// (max.y - min.y)
// (max.z - min.z)
let maxDistance = 0;
let indexMax = 0;
for (i = 0; i < 3; i += 1) {
const distance = max[i].point[i] - min[i].point[i];
if (distance > maxDistance) {
maxDistance = distance;
indexMax = i;
}
}
// eslint-disable-next-line prefer-const
v0 = min[indexMax];
// eslint-disable-next-line prefer-const
v1 = max[indexMax];
// the next vertex is the one farthest to the line formed by `v0` and `v1`
maxDistance = 0;
for (i = 0; i < this.vertices.length; i += 1) {
const vertex = this.vertices[i];
if (vertex !== v0 && vertex !== v1) {
const distance = pointLineDistance(
vertex.point,
v0.point,
v1.point
);
if (distance > maxDistance) {
maxDistance = distance;
v2 = vertex;
}
}
}
// the next vertes is the one farthest to the plane `v0`, `v1`, `v2`
// normalize((v2 - v1) x (v0 - v1))
const normal = getPlaneNormal([], v0.point, v1.point, v2?.point || []);
// distance from the origin to the plane
const distPO = dot(v0.point, normal);
maxDistance = -1;
for (i = 0; i < this.vertices.length; i += 1) {
const vertex = this.vertices[i];
if (vertex !== v0 && vertex !== v1 && vertex !== v2) {
const distance = Math.abs(dot(normal, vertex.point) - distPO);
if (distance > maxDistance) {
maxDistance = distance;
v3 = vertex;
}
}
}
// initial simplex
// Taken from http://everything2.com/title/How+to+paint+a+tetrahedron
//
// v2
// ,|,
// ,7``\'VA,
// ,7` |, `'VA,
// ,7` `\ `'VA,
// ,7` |, `'VA,
// ,7` `\ `'VA,
// ,7` |, `'VA,
// ,7` `\ ,..ooOOTK` v3
// ,7` |,.ooOOT''` AV
// ,7` ,..ooOOT`\` /7
// ,7` ,..ooOOT''` |, AV
// ,T,..ooOOT''` `\ /7
// v0 `'TTs., |, AV
// `'TTs., `\ /7
// `'TTs., |, AV
// `'TTs., `\ /7
// `'TTs., |, AV
// `'TTs.,\/7
// `'T`
// v1
//
const faces = [];
if (dot(v3?.point || [], normal) - distPO < 0) {
// the face is not able to see the point so `planeNormal`
// is pointing outside the tetrahedron
if (!v3) throw new Error("v3 is not defined");
if (!v2) throw new Error("v2 is not defined");
if (!v1) throw new Error("v1 is not defined");
faces.push(
Face.createTriangle(v0, v1, v2),
Face.createTriangle(v3, v1, v0),
Face.createTriangle(v3, v2, v1),
Face.createTriangle(v3, v0, v2)
);
// set the opposite edge
for (i = 0; i < 3; i += 1) {
const j = (i + 1) % 3;
// join face[i] i > 0, with the first face
if (!faces[0]) throw new Error("faces[0] is not defined");
if (!faces[j + 1]) throw new Error("faces[i] is not defined");
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
faces[i + 1].getEdge(2)?.setOpposite(faces[0].getEdge(j)!);
// join face[i] with face[i + 1], 1 <= i <= 3
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
faces[i + 1].getEdge(1)?.setOpposite(faces[j + 1].getEdge(0)!);
}
} else {
// the face is able to see the point so `planeNormal`
// is pointing inside the tetrahedron
if (!v3) throw new Error("v3 is not defined");
if (!v2) throw new Error("v2 is not defined");
if (!v1) throw new Error("v1 is not defined");
faces.push(
Face.createTriangle(v0, v2, v1),
Face.createTriangle(v3, v0, v1),
Face.createTriangle(v3, v1, v2),
Face.createTriangle(v3, v2, v0)
);
// set the opposite edge
for (i = 0; i < 3; i += 1) {
const j = (i + 1) % 3;
// join face[i] i > 0, with the first face
faces[i + 1]
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
.getEdge(2)
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
?.setOpposite(faces[0].getEdge((3 - i) % 3)!);
// join face[i] with face[i + 1]
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
faces[i + 1].getEdge(0)?.setOpposite(faces[j + 1].getEdge(1)!);
}
}
// the initial hull is the tetrahedron
for (i = 0; i < 4; i += 1) {
this.faces.push(faces[i]);
}
// initial assignment of vertices to the faces of the tetrahedron
for (i = 0; i < vertices.length; i += 1) {
const vertex = vertices[i];
if (
vertex !== v0 &&
vertex !== v1 &&
vertex !== v2 &&
vertex !== v3
) {
maxDistance = this.tolerance;
let maxFace;
for (j = 0; j < 4; j += 1) {
const distance = faces[j].distanceToPlane(vertex.point);
if (distance > maxDistance) {
maxDistance = distance;
maxFace = faces[j];
}
}
if (maxFace) {
this.addVertexToFace(vertex, maxFace);
}
}
}
}
reindexFaceAndVertices() {
// remove inactive faces
const activeFaces = [];
for (let i = 0; i < this.faces.length; i += 1) {
const face = this.faces[i];
if (face.mark === VISIBLE) {
activeFaces.push(face);
}
}
this.faces = activeFaces;
}
collectFaces(skipTriangulation: boolean) {
const faceIndices = [];
for (let i = 0; i < this.faces.length; i += 1) {
if (this.faces[i].mark !== VISIBLE) {
throw Error("attempt to include a destroyed face in the hull");
}
const indices = this.faces[i].collectIndices();
if (skipTriangulation) {
faceIndices.push(indices);
} else {
for (let j = 0; j < indices.length - 2; j += 1) {
faceIndices.push([
indices[0],
indices[j + 1],
indices[j + 2],
]);
}
}
}
return faceIndices;
}
/**
* Finds the next vertex to make faces with the current hull
*
* - let `face` be the first face existing in the `claimed` vertex list
* - if `face` doesn't exist then return since there're no vertices left
* - otherwise for each `vertex` that face sees find the one furthest away
* from `face`
*
* @return {Vertex|undefined} Returns undefined when there're no more
* visible vertices
*/
nextVertexToAdd() {
if (!this.claimed.isEmpty()) {
let eyeVertex, vertex;
let maxDistance = 0;
const eyeFace = this.claimed.first()?.face;
for (
vertex = eyeFace?.outside;
vertex && vertex.face === eyeFace;
vertex = vertex.next
) {
const distance = eyeFace?.distanceToPlane(vertex.point) || 0;
if (distance > maxDistance) {
maxDistance = distance;
eyeVertex = vertex;
}
}
return eyeVertex;
}
}
/**
* Computes a chain of half edges in ccw order called the `horizon`, for an
* edge to be part of the horizon it must join a face that can see
* `eyePoint` and a face that cannot see `eyePoint`
*
* @param {number[]} eyePoint - The coordinates of a point
* @param {HalfEdge} crossEdge - The edge used to jump to the current `face`
* @param {Face} face - The current face being tested
* @param {HalfEdge[]} horizon - The edges that form part of the horizon in
* ccw order
*/
computeHorizon(
eyePoint: number[],
crossEdge: HalfEdge,
face: Face,
horizon: HalfEdge[]
) {
// moves face's vertices to the `unclaimed` vertex list
this.deleteFaceVertices(face, new Face());
face.mark = DELETED;
let edge;
if (!crossEdge) {
edge = crossEdge =
face.getEdge(0) || new HalfEdge(new Vertex([], 0), new Face());
} else {
// start from the next edge since `crossEdge` was already analyzed
// (actually `crossEdge.opposite` was the face who called this method
// recursively)
edge = crossEdge.next;
}
// All the faces that are able to see `eyeVertex` are defined as follows
//
// v /
// / <== visible face
// /
// |
// | <== not visible face
//
// dot(v, visible face normal) - visible face offset > this.tolerance
//
do {
const oppositeEdge = edge?.opposite;
const oppositeFace = oppositeEdge?.face;
if (!oppositeEdge) throw new Error("oppositeEdge is not defined");
if (oppositeFace?.mark === VISIBLE) {
if (oppositeFace.distanceToPlane(eyePoint) > this.tolerance) {
this.computeHorizon(
eyePoint,
oppositeEdge,
oppositeFace,
horizon
);
} else {
if (edge) horizon.push(edge);
}
}
edge = edge?.next;
} while (edge !== crossEdge);
}
/**
* Creates a face with the points `eyeVertex.point`, `horizonEdge.tail` and
* `horizonEdge.tail` in ccw order
*
* @param {Vertex} eyeVertex
* @param {HalfEdge} horizonEdge
* @return {HalfEdge} The half edge whose vertex is the eyeVertex
*/
addAdjoiningFace(eyeVertex: Vertex, horizonEdge: HalfEdge) {
// all the half edges are created in ccw order thus the face is always
// pointing outside the hull
// edges:
//
// eyeVertex.point
// / \
// / \
// 1 / \ 0
// / \
// / \
// / \
// horizon.tail --- horizon.head
// 2
//
const face = Face.createTriangle(
eyeVertex,
horizonEdge.tail() || new Vertex([], 0),
horizonEdge.head()
);
this.faces.push(face);
// join face.getEdge(-1) with the horizon's opposite edge
// face.getEdge(-1) = face.getEdge(2)
face.getEdge(-1)?.setOpposite(
horizonEdge.opposite || new HalfEdge(new Vertex([], 0), new Face())
);
return face.getEdge(0);
}
/**
* Adds horizon.length faces to the hull, each face will be 'linked' with the
* horizon opposite face and the face on the left/right
*
* @param {Vertex} eyeVertex
* @param {HalfEdge[]} horizon - A chain of half edges in ccw order
*/
addNewFaces(eyeVertex: Vertex, horizon: HalfEdge[]) {
this.newFaces = [];
let firstSideEdge, previousSideEdge;
for (let i = 0; i < horizon.length; i += 1) {
const horizonEdge = horizon[i];
// returns the right side edge
const sideEdge = this.addAdjoiningFace(eyeVertex, horizonEdge);
if (!firstSideEdge) {
firstSideEdge = sideEdge;
} else {
// joins face.getEdge(1) with previousFace.getEdge(0)
sideEdge?.next?.setOpposite(
previousSideEdge ||
new HalfEdge(new Vertex([], 0), new Face())
);
}
this.newFaces.push(sideEdge?.face || new Face());
previousSideEdge = sideEdge;
}
firstSideEdge?.next?.setOpposite(
previousSideEdge || new HalfEdge(new Vertex([], 0), new Face())
);
}
/**
* Computes the distance from `edge` opposite face's centroid to
* `edge.face`
*
* @param {HalfEdge} edge
* @return {number}
* - A positive number when the centroid of the opposite face is above the
* face i.e. when the faces are concave
* - A negative number when the centroid of the opposite face is below the
* face i.e. when the faces are convex
*/
oppositeFaceDistance(edge: HalfEdge) {
return edge?.face?.distanceToPlane(edge.opposite?.face?.centroid || []);
}
/**
* Merges a face with none/any/all its neighbors according to the strategy
* used
*
* if `mergeType` is MERGE_NON_CONVEX_WRT_LARGER_FACE then the merge will be
* decided based on the face with the larger area, the centroid of the face
* with the smaller area will be checked against the one with the larger area
* to see if it's in the merge range [tolerance, -tolerance] i.e.
*
* dot(centroid smaller face, larger face normal) - larger face offset > -tolerance
*
* Note that the first check (with +tolerance) was done on `computeHorizon`
*
* If the above is not true then the check is done with respect to the smaller
* face i.e.
*
* dot(centroid larger face, smaller face normal) - smaller face offset > -tolerance
*
* If true then it means that two faces are non convex (concave), even if the
* dot(...) - offset value is > 0 (that's the point of doing the merge in the
* first place)
*
* If two faces are concave then the check must also be done on the other face
* but this is done in another merge pass, for this to happen the face is
* marked in a temporal NON_CONVEX state
*
* if `mergeType` is MERGE_NON_CONVEX then two faces will be merged only if
* they pass the following conditions
*
* dot(centroid smaller face, larger face normal) - larger face offset > -tolerance
* dot(centroid larger face, smaller face normal) - smaller face offset > -tolerance
*
* @param {Face} face
* @param {number} mergeType - Either MERGE_NON_CONVEX_WRT_LARGER_FACE or
* MERGE_NON_CONVEX
*/
doAdjacentMerge(face: Face, mergeType: number) {
let edge = face.edge;
let convex = true;
let it = 0;
do {
if (it >= face.nVertices) {
throw Error("merge recursion limit exceeded");
}
const oppositeFace = edge?.opposite?.face;
let merge = false;
// Important notes about the algorithm to merge faces
//
// - Given a vertex `eyeVertex` that will be added to the hull
// all the faces that cannot see `eyeVertex` are defined as follows
//
// dot(v, not visible face normal) - not visible offset < tolerance
//
// - Two faces can be merged when the centroid of one of these faces
// projected to the normal of the other face minus the other face offset
// is in the range [tolerance, -tolerance]
// - Since `face` (given in the input for this method) has passed the
// check above we only have to check the lower bound e.g.
//
// dot(v, not visible face normal) - not visible offset > -tolerance
//
if (mergeType === MERGE_NON_CONVEX) {
if (
(this.oppositeFaceDistance(
edge || new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance ||
(this.oppositeFaceDistance(
edge?.opposite ||
new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance
) {
merge = true;
}
} else {
if (face.area > (oppositeFace?.area || 0)) {
if (
(this.oppositeFaceDistance(
edge || new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance
) {
merge = true;
} else if (
(this.oppositeFaceDistance(
edge?.opposite ||
new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance
) {
convex = false;
}
} else {
if (
(this.oppositeFaceDistance(
edge?.opposite ||
new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance
) {
merge = true;
} else if (
(this.oppositeFaceDistance(
edge || new HalfEdge(new Vertex([], 0), new Face())
) || 0) > -this.tolerance
) {
convex = false;
}
}
}
if (merge) {
debug("face merge");
// when two faces are merged it might be possible that redundant faces
// are destroyed, in that case move all the visible vertices from the
// destroyed faces to the `unclaimed` vertex list
const discardedFaces = face.mergeAdjacentFaces(
edge || new HalfEdge(new Vertex([], 0), new Face()),
[]
);
for (let i = 0; i < discardedFaces.length; i += 1) {
this.deleteFaceVertices(
discardedFaces[i] || new Face(),
face
);
}
return true;
}
edge = edge?.next || null;
it += 1;
} while (edge !== face.edge);
if (!convex) {
face.mark = NON_CONVEX;
}
return false;
}
/**
* Adds a vertex to the hull with the following algorithm
*
* - Compute the `horizon` which is a chain of half edges, for an edge to
* belong to this group it must be the edge connecting a face that can
* see `eyeVertex` and a face which cannot see `eyeVertex`
* - All the faces that can see `eyeVertex` have its visible vertices removed
* from the claimed VertexList
* - A new set of faces is created with each edge of the `horizon` and
* `eyeVertex`, each face is connected with the opposite horizon face and
* the face on the left/right
* - The new faces are merged if possible with the opposite horizon face first
* and then the faces on the right/left
* - The vertices removed from all the visible faces are assigned to the new
* faces if possible
*
* @param {Vertex} eyeVertex
*/
addVertexToHull(eyeVertex: Vertex) {
const horizon: HalfEdge[] = [];
this.unclaimed.clear();
// remove `eyeVertex` from `eyeVertex.face` so that it can't be added to the
// `unclaimed` vertex list
this.removeVertexFromFace(eyeVertex, eyeVertex.face || new Face());
this.computeHorizon(
eyeVertex.point,
new HalfEdge(new Vertex([], 0), new Face()),
eyeVertex.face || new Face(),
horizon
);
if (debug.enabled) {
debug(
"horizon %j",
horizon.map(function (edge) {
return edge.head().index;
})
);
}
this.addNewFaces(eyeVertex, horizon);
debug("first merge");
// first merge pass
// Do the merge with respect to the larger face
for (let i = 0; i < this.newFaces.length; i += 1) {
const face = this.newFaces[i];
if (face.mark === VISIBLE) {
while (
this.doAdjacentMerge(face, MERGE_NON_CONVEX_WRT_LARGER_FACE)
) {
void 0;
}
}
}
debug("second merge");
// second merge pass
// Do the merge on non convex faces (a face is marked as non convex in the
// first pass)
for (let i = 0; i < this.newFaces.length; i += 1) {
const face = this.newFaces[i];
if (face.mark === NON_CONVEX) {
face.mark = VISIBLE;
while (this.doAdjacentMerge(face, MERGE_NON_CONVEX)) {
void 0;
}
}
}
debug("reassigning points to newFaces");
// reassign `unclaimed` vertices to the new faces
this.resolveUnclaimedPoints(this.newFaces);
}
build() {
let iterations = 0;
let eyeVertex;
this.createInitialSimplex();
while ((eyeVertex = this.nextVertexToAdd())) {
iterations += 1;
debug("== iteration %j ==", iterations);
debug(
"next vertex to add = %d %j",
eyeVertex.index,
eyeVertex.point
);
this.addVertexToHull(eyeVertex);
debug("end");
}
this.reindexFaceAndVertices();
}
/**
*
* @typedef {Object} Vector3
* @property {Number} x
* @property {Number} y
* @property {Number} z
*/
/**
*
* @param {Array<Vector3 | Array<Number>} points
* @returns {Array<Array<Number>>}
*/
static createHull(points: number[][]) {
points = points.slice();
for (let pti = 0; pti < points.length; pti++) {
const pt = points[pti];
if (!Array.isArray(pt)) {
points[pti] = [pt[0], pt[1], pt[2]];
}
}
const hull = new QuickHull(points);
hull.build();
const faces = hull.collectFaces(false);
return faces;
}
}
export default QuickHull; |
|
Nice. My only complaint with the conversion is that with the createHull function, it can no longer take an array of number triplets or an array of vectors. Other than that, good job on the conversion. |
|
@Dannie226 Then I think I might add a conversion utility to convert vectors/triplets to numbers, then implement it internally. I'm going to create a GitHub repo and NPM package for this. https://github.com/RedstoneWizard08/QuickHull.git |
|
Added the vertex conversion |
|
Ok, I made the NPM package |
|
try initializing max distance to -1, not 0 |
|
Ok |
|
That worked! Thanks! Fixing the bug under version 1.0.2 |
|
Let's move this conversation over to the quickhull repo that you made because technically, this conversation isn't directly part of improving the cannon-es convex polyhedron creation |
|
Okay. |
|
@marcofugaro, it's been a while since a message on this issue, but I created a pull request for integration of a convex hull from a set of points. The pull request can be found here, and I would very much like to see some progress in this area. Even if it isn't this exact thing, I would still like some progress. |
|
Thank you for brilliant code @Dannie226 and to other contributors! |
|
Because of the way that the built-in convex polyhedron works, there is no way to get what you are asking for. A convex polyhedron will always push a body away from its center, so, if you have a body on the inside of a convex polyhedron, the body will be pushed outside of it. |
Greeting to every master! Now I am applying the react-three-cannon to do the collision. Two objects are all using useConvexPolyhedron from react three cannon to create convex colliders. At first,I have the error that "Cannot read property 'x' of undefined". But After I use the Quickhull.js provided on the other master to create the face value,It's alright. Although it still performance to bad after two objects hit together. Did anyone face this before and have some solutions or suggestions for it ? It will be a good help for me, Thanks! Here is the link to check the video Here is the code snippet |
|
Greetings everyone. Convex polyhedron never behaved correctly for me with more complex shapes. To fix this, I created a Python script with blender that parses the boxes in a collection, which you should name "Colliders," then it will print out json format text in the console, and using that json file I parse it and generate the proper box colliders in my game. Here is the blender python script: import bpy
import math
collection = bpy.data.collections.get("Colliders")
# Get all objects in the scene
all_objects = collection.objects
# Count meshes for formatting
meshCount = 0
for obj in all_objects:
if obj.type == 'MESH':
meshCount += 1
# Print mesh information using ID counter
objectID = 0
print("{")
for obj in all_objects:
if obj.type == 'MESH':
print(" \"box_" + str(objectID) + "\":{")
# Position
position = obj.location
print(" \"position\":{")
print(" \"x\":" + str(position.x) + ",")
print(" \"y\":" + str(position.y) + ",")
print(" \"z\":" + str(position.z))
print(" },")
# Scale
scale = obj.scale
print(" \"scale\":{")
print(" \"x\":" + str(scale.x) + ",")
print(" \"y\":" + str(scale.y) + ",")
print(" \"z\":" + str(scale.z))
print(" },")
# Rotation (Euler)
rotation = obj.rotation_euler
print(" \"rotation\":{")
print(" \"x\":" + str(math.degrees(rotation.x)) + ",")
print(" \"y\":" + str(math.degrees(rotation.y)) + ",")
print(" \"z\":" + str(math.degrees(rotation.z)))
print(" }")
if(objectID != meshCount - 1):
print(" },\n")
else:
print(" }")
objectID += 1
print("}")That will generate the json text. Copy that from your console, paste it in a .json file, and parse it like so in a js file with cannon: /*
* Creating the level collision geometry
*/
async function GenerateLevelColliders(){
// RigidBody
levelRigidbody = new CANNON.Body({
type: CANNON.Body.STATIC
});
// Parse the JSON file
await fetch("levelColliders/level_" + currentLevel + ".json")
.then(response => response.json())
.then(data => {
let boxID = 0;
for (let boxKey in data) {
if(data.hasOwnProperty(boxKey)){
const box = data[boxKey];
const position = box.position;
const scale = box.scale;
const rotation = box.rotation;
let boxShape = new CANNON.Box(new CANNON.Vec3(scale.x, scale.y, scale.z));
// Set the last box as the "checkpoint"
if(boxID == Object.keys(data).length - 1){
// Create a specific body for final shape
levelEndRigidbody = new CANNON.Body({
type: CANNON.Body.STATIC
});
// Add its box
levelEndRigidbody.addShape(
boxShape,
new CANNON.Vec3(position.x , position.z, -position.y), // ~ Y is up in blender
EulerToQuaternion(rotation.x + 90, rotation.z, -rotation.y)
);
} else {
// Add each other box given position, scale and rotation
levelRigidbody.addShape(
boxShape,
new CANNON.Vec3(position.x , position.z, -position.y), // ~ Y is up in blender
EulerToQuaternion(rotation.x + 90, rotation.z, -rotation.y)
);
}
boxID += 1;
}
}
})
.catch(error => {
console.error('Error parsing JSON file:', error);
});
// Add the bodies
PhysicsWorld.addBody(levelRigidbody);
PhysicsWorld.addBody(levelEndRigidbody);
console.log("Finished loading: levelColliders/level_" + currentLevel + ".json ☑");
}Keep in mind you must:
Hope this is helpful for game devs building larger levels with a bunch of colliders. The only downside to this is your colliders will use only boxes as primitives, but I'm sure this pipeline can be applied to spheres, and even tris. |
|
Hi @Dannie226 , I am using the code you provided but getting a weird error. |
|
@RedstoneWizard08, i dont think this will solve the issue I am facing- I have a threejs mesh and am extracting the vertices and faces data from it to create a convex polyhedron and a collision between 2 such convex polyhedron is giving me an error- |
|
You are not passing the parameters in properly. It should be an object with a vertices and a faces property, not 2 separate parameters. So, this line let myShape = new CANNON.ConvexPolyhedron(points, myfaces);should be let myShape = new CANNON.ConvexPolyhedron({vertices: points, faces: myfaces});As long as my spelling is correct, then that should work. |
|
@Dannie226 , I have edited the function but now I am getting a completely different error - |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hey,
First of all, this is a duplicate issue from another repository (three-to-cannon) that seems like to be not related to it at all.
I used three-to-cannon first, then I switch for another method manually, both gave me the same results.
The error
Uncaught TypeError: Cannot read property 'x' of undefined at Vec3.copy (cannon-es.js:915) at ConvexPolyhedron.clipFaceAgainstHull (cannon-es.js:2593) at ConvexPolyhedron.clipAgainstHull (cannon-es.js:2335) at Narrowphase.convexConvex (cannon-es.js:11067) at Narrowphase.getContacts (cannon-es.js:10759) at World.internalStep (cannon-es.js:12774) at World.step (cannon-es.js:12650) at animate (index.js:149)I've been getting this error when two bodies with the hull settings collide with each other. My knowledge about geometries is pretty low, so I don't really understand what is happening. I found this (schteppe#459) in the CannonJS issues tab, might be useful.
Edit: I forgot to say that I merged the vertices as user "Dannie226" said, and it didn't change the problem, so I'm assuming that the fact that I'm using cannon-es is the whole reason it didn't solved it.
Any help would be greatly appreciated!
The text was updated successfully, but these errors were encountered: