collinhover / threeoctree

(sparse + dynamic) 3D spatial representation structure for fast searches

collinhover.github.io

Leader & Engineer in Gaming + Software + Web

threeoctree's Issues

About Octree search issues

1.octree.add(group);
2.this.octree.search returns null
3. Because my group contains multiple objects, how can I handle the problem?
Thank you

Question: which parts of this repository are broken for latest three.js build

In the docs is written:

This build is stable up to THREE.js ~r60

I would like to know which parts of this repository are not working with the latest build of three.js. Can I not use threeoctree at all in r78? Or are only some of the features broken?

I don't mind contributing with some PR's to help get the repository up to date (when I have some time to kill) with latest three.js but then it would be good to know in advance which parts need attention.

Expected object missing in `octreeResults` array when using `useVertices: true`

I know you are very busy @collinhover but I hope you could be so kind to shortly look into this issue.

Prior to making a PR for the other issue that I posted (about optional parameter for sorting objects, which is actually an easy fix), I was working with your Octree library to wrap my head around it.

I had some serious issues with the octree search results inside my project when setting useVertices to true. To isolate the issue and to make sure the issue wasn't caused by my own code I made a fiddle in which I was able to reproduce this issue.

https://jsfiddle.net/wilt/8jeu2ykg/

When hovering with the mouse on the beam at the location of the white arrow in the screenshot below, the diagonal beam is missing from the octreeResults set. I could work on a PR for this, but I actually have no idea what is causing this issue. Can you give some guidance on where to look for the problem for this specific case?
The funny thing is when setting useVertices to false (line 138 in the fiddle) all is fine; in that case the beam is in the result set as expected...

Note: In my fiddle I implemented the sort method in this example very simply with array sort method:

intersects.sort(function(a, b) {
    return a.distance - b.distance;
});

But this cannot be causing the issue, since the actual diagonal beam is already missing in the octreeResult set (see also the output in the console)...

octree.search assigns most distant object to first index

Hi Collin, great work on the octree! It's fantastically useful for me :)

I noticed there is a bug when the ray object has a negative z coordinate, the octree.search returns the most distant object first, from the scene.

How to search within subnodes?

Your library is AWESOME! It allows me to continue my game as I really need realtime ray picking.
My character is walking on a terrain, which consists of 9 meshes (chunks) that are placed in a 3x3 grid. I added the triangles of all meshes to an octree.

This is working great, my only question is if it'd be better if you could search from a starting node instead of the main octree? For instance, I already know that my character is standing on one terrain mesh within the 3x3 grid, so I'd only need to check the triangles of that mesh instead of the triangles of all 3x3 terrain meshes? Or does your library already manage all that under the hood?

EDIT: just thought of something...Perhaps I could simply add a new THREE.Octree() for each mesh I make?

Issues with octree search radius

Hello,
I am currently experimenting with three.js and your octree to make my third-person camera collision more efficient, but when I wanted to highlight objects being found in that radius, I noticed they are always highlighted.

I have 6 objects in the octree and even if the distance of player.position and an object is greater than defaultDistance it is contained in octreeResult:

   var rayDirection = camera.matrixWorld.multiplyVector3(new THREE.Vector3()).subSelf(player.position).normalize();
   var ray = new THREE.Ray(player.position, rayDirection, 0, camera.defaultDistance); // defaultDistance 200
   var octreeResults = octree.search(player.position, camera.defaultDistance, true, rayDirection);
   if (octreeResults < 6) console.log(octreeResults.length); // never triggered!

threeOctree is not available as npm Module

Loading the tree with 10,000+ objects is slow

We have a game that has over 100k objects in the scene. That get rendered when the game loads. Each of these objects can be looked up by ID. All of these have to be added to the Octree when the game loads. Initially I was creating a new Object3D for each of these objects so the Octree could get their position and radius. However the overhead of creating thousands of THREE.Object3D was very high around 350ms on a fast processor.

So I realized all the THREE.OctreeObjectData needs is the position and the radius of the object, so if I could set those in a generic way it would save a ton of object creation time. I modified THREE.OctreeObjectData to fall back to this generic object if it's not a THREE.Object3D and it made it about 200ms faster! Which is a noticeable difference.

I'm pushing a my pull request for this.

Library needs to be updated to latest ThreeJS version

Getting the error: "Octree.js:2094 Uncaught TypeError: Cannot read property 'faces' of undefined".
I'm pretty sure this is because the library is out of date.

My temporary fix (to help anyone else affected by this) is to change line 2085 to be:
if ( object.object instanceof THREE.Object3D ) { return this.intersectOctreeObject(object.object, recursive);

The "return this.intersectOctreeObject" forces it to keep recursing until it finds the type of non-octree object it's looking for.

Anyways, thought I'd let you know. I'd also like an updated version of the library in case I run into some weird edge cases in the future.

rebuild() doesn't remove nodes for moderate face count

I'm rotation an object 90 degrees and back, and at each step I call octree.rebuild(). It's adding nodes correctly (as far as I can tell), but it rarely removes old nodes. So when it gets back to it's original orientation the octree is a mess.

This problem doesn't occur when the face count is very low. It works fine for a model with 14 faces, but the problem occurs with 519 faces.

My system is not very powerful, so it might not occur with this low face count for other people.

Starting octree:

Ending octree (after rotate 90 and back):

octree raycasting returns unordered intersects array

This issue can also be noticed in this example:

http://threejs.org/examples/webgl_octree_raycasting.html

When hovering with the mouse on (some of the) boxes in front of the statue the statue is highlighted. This is caused by the fact that the intersects array that is returned by the intersectOctreeObjects method is not ordering the results. This behavior is different from normal raycasting where the objects are ordered (closest object is first in the array).

Is this intentional?
Or can the code be updated to return objects in an ordered array?

Issues running example.html

Hey i'm sure this is a silly question but I can't seem to get any output when I run example.html, I keep getting this error (Uncaught TypeError: Cannot read property 'radius' of null ). Please advise.

Get Face Index

Im trying to retrieve the index of the face from the octree.search function. Any ideas on how to find it.

I have a bufferGeometry that i convert to geometry, Create an octree from and search. I then want to toss the octree and geometry mesh away and go back to using my buffer geometry. But can not find a way to correlate the octree face results to the indexed bufferGeometry.

I do notice that faces are the same as indexes in bufferGoemetry and geometry( geometry.faces[i].a = bufferGeometry.index.array[i*3+0] )

Current Dumb Loop

octreeFaces: for (var octreeFaceIndex = 0; octreeFaceIndex < octreeResult.length; octreeFaceIndex++)
	for (
		var indexIndex = parseInt(surface.geometry.index.array.indexOf(octreeResult[octreeFaceIndex].faces.a) / 3) * 3,
		lastIndexIndex = parseInt(surface.geometry.index.array.lastIndexOf(octreeResult[octreeFaceIndex].faces.a) / 3) * 3;
                indexIndex < lastIndexIndex;
                indexIndex += 3
	) {
		if (
			surface.geometry.index.array[indexIndex + 0] == octreeResult[octreeFaceIndex].faces.a &&
			surface.geometry.index.array[indexIndex + 1] == octreeResult[octreeFaceIndex].faces.b &&
			surface.geometry.index.array[indexIndex + 2] == octreeResult[octreeFaceIndex].faces.c
		) {
			indexes2check.push(indexIndex);
			console.log(surface.geometry.index.array[indexIndex + 0], surface.geometry.index.array[indexIndex + 1], surface.geometry.index.array[indexIndex + 2])
			console.log(indexIndex, octreeResult[octreeFaceIndex])
			console.log('FOUND')
			continue octreeFaces;
		}
          }

BufferGeometry support

I noticed that there's no support for BufferGeometry (both for point cloud and faces). Is the lack of support intentional or just on the "todo" list?

I can see where it might go in the addDeferred() function. Although not 100% sure how automated it can be made (perhaps the options need to include parameter to treat the buffergeometry as a point cloud, triangle, and/or from which bufferattribute to read from).

Fetching the intersection point

Hello! Before I ask a question I just need to say I appreciate the octree you've done, amazing work.

After typing this:

var octree = new THREE.Octree({
                scene: scene
            });

octree.add(world, true); //world is a sphere mesh

var rayCaster = new THREE.Raycaster(new THREE.Vector3(0, 0, 0), new THREE.Vector3(1,1, 1));
var octreeResults = octree.search(rayCaster.ray.origin, rayCaster.ray.far, true,  rayCaster.ray.direction);
var octreeIntersect = rayCaster.intersectOctreeObject(octreeResults);

What kind of object is octreeIntersect supposed to be?

I thought it returned the intersect object with variables such as distance, face, point etc. But they seem undefined. Maybe I've missed something. I'm shooting rays from inside a doublesided sphere so they should never miss. How do you use octreeIntersect to find the point for example?

Thanks.
Lalle

Broken link

The README.md for this Github repository has a broken link that needs to be updated.

Distance to searched object greater than radius

Hi Collin, great job building this.

I'm not familiar with spatial geometry, and I've tried experimenting your Octree for getting objects near another object.

When I run octree.search(object, 100)[0].position.distanceTo(object), I can get figures ranging up to 1300 as a result (objects are scattered randomly). Can that be normal behavior? I'll dig into it again, but if you have an idea why that might happen, that would sure help!

Use distanceSquared in findClosestVertex

Was wondering if this would be a valid PR?

line 590:
distance = vertices[i].distanceTo(localPosition);
change to:
distance = vertices[i].distanceToSquared(localPosition);