Raycaster only works on the first triangle of the BufferGeometry

[unphased]

Description of the problem

I have textured quads built using BufferGeometry with 4 vertices. It is in fact rendered using rasterMesh.drawMode = THREE.TriangleFanDrawMode.

Three.js version

• r79
• r81
• Dev

Browser

• All of them
• Chrome
• Firefox
• Internet Explorer

OS

• All of them
• Windows
• Linux
• Android
• IOS

Hardware Requirements (graphics card, VR Device, ...)

[unphased]

Confirmed. When switching the quad geometry to 6 verts the raycast works properly.

[WestLangley]

Hmm... It appears Mesh.raycast() implicitly assumes drawMode is TrianglesDrawMode.

[tsbehlman]

Indeed, for indexed and non-indexed geometry

three.js/src/objects/Mesh.js

Lines 275 to 281 in dcfc3a3

	for ( i = 0, l = position.count; i < l; i += 3 ) {
	a = i;
	b = i + 1;
	c = i + 2;
	intersection = checkBufferGeometryIntersection( this, raycaster, ray, position, uv, a, b, c );

[glockjt]

Is there a fix coming for this or a work around? I am using CylinderBufferGeometry and BoxBufferGeometry and can only get an intersection on one triangle of the shapes.

[WestLangley]

@glockjt This thread is about supporting alternate draw modes, and is unrelated to your problem if you are using the geometries you say you are.

[Mugen87]

The book WebGL Insights does not recommend to use TRIANGLE_FAN:

Avoid use of gl.TRIANGLE_FAN, as it may be emulated in software.

That makes we wonder if we should not just removed Mesh.drawMode and always work with TRIANGLES. I've seen very few use cases so far where Mesh.drawMode is actually changed by users.

[WestLangley]

That makes we wonder if we should not just removed Mesh.drawMode and always work with TRIANGLES.

The glTF spec requires support for all draw modes.

If the renderer is not going to support all draw modes directly, I assume it will need to convert the geometry to triangles draw mode automatically...

[Mugen87]

@donmccurdy How common is the usage of the primitive modes TRIANGLE_STRIP and TRIANGLE_FAN in glTF? What do you think about converting them to TRIANGLES with helper methods?

[donmccurdy]

The glTF spec requires support for all draw modes.

I think we should aim to support models that were authored with other draw modes, but that's not (necessarily) to say we couldn't convert them and render with TRIANGLES, if the visual result is the same.

How common is the usage of the primitive modes TRIANGLE_STRIP and TRIANGLE_FAN in glTF?

I don't know, unfortunately. No idea how you would create one using a DCC tool, anyway. Threads like this make me think it's not a particularly common optimization ([Unity's] MeshTopology.TriangleStrip was removed for reasons unknown ), but I don't have numbers here.

What do you think about converting them to TRIANGLES with helper methods?

Did you have in mind that the conversion would be done by GLTFLoader, or by the renderer? I wouldn't want it to be in the renderer, I don't think – users should be able to assume that if they've made a valid BufferGeometry, it is GPU-ready.

Another option would be to begin warning in the raycaster, provide users methods to convert, and see if there are users for whom that doesn't work well enough.

[Mugen87]

Another option would be to begin warning in the raycaster, provide users methods to convert, and see if there are users for whom that doesn't work well enough.

That's sounds like a good idea to me!

[donmccurdy]

Perhaps relevant, from https://github.com/zeux/meshoptimizer#triangle-strip-conversion —

On most hardware, indexed triangle lists are the most efficient way to drive the GPU. However, in some cases triangle strips might prove beneficial:

• On some older GPUs, triangle strips may be a bit more efficient to render
• On extremely memory constrained systems, index buffers for triangle strips could save a bit of memory

I don't find that entirely compelling, but definitely helpful as the only resource I've found on it.

[Mugen87]

Okay, we have now a helper function which can convert the draw modes of geometries to gl.TRIANGLES. Hence, I suggest to close the issue and refer to BufferGeometryUtils.toTrianglesDrawMode() from now on.

We should consider in a new issue to completely remove drawMode from Mesh and always use gl.TRIANGLES. Loaders like GLTFLoader would have to perform a draw mode conversion via BufferGeometryUtils.toTrianglesDrawMode() if necessary. AFAIK, it's the only loader that actually sets Mesh.drawMode.

[WestLangley]

We should consider in a new issue to completely remove drawMode from Mesh and always use gl.TRIANGLES.

I think that is reasonable.

[mrdoob]

I think that sounds good to me too.

As far as I can remember, it was @fernandojsg that added that functionality for A-Painter but we were not aware of all the ramifications.

[Mugen87]

Some more thoughts about this topic:

In context of lines, we have Line, LineLoop and LineSegments which implicitly encode the draw mode and other primitive specific information (e.g line distances).

In Mesh, we just have a drawMode property instead. So the current design was never consistent. It would be if there were something like TriangleMesh, TriangleFanMesh and TriangleStripMesh. But I don't think it's beneficial to have such classes.

[Mugen87]

Mesh.drawMode has been removed. Please check the migration guide for R112 to see the recommended migration task.

https://github.com/mrdoob/three.js/wiki/Migration-Guide#r111--r112

[Dmarcoux111]

@Mugen87 I have a situation where I have to generate heightmapped tiles pretty efficiently, and save memory with indices and triangleStrips ( https://www.learnopengles.com/tag/index-buffer-object/ ). I do my raycasting somewhere else and would kinda like to see this feature come back.

[mrdoob]

What feature?

[Dmarcoux111]

Triangle Strip draw mode

*maybe im in the wrong place, but i upgraded from 110 and now i get an error which points to the migration guide ( super helpful btw ), which said that from now on you have to use triangles because triangle strips arent supported

[Mugen87]

The support for triangle strip and fan was very limited in the past and improving this situation would have been caused many enhancements in the core (quickly leading to over-engineering). Read #18041 for more information about this topic. I think it's unlikely to bring triangle strip and fan back to the core.

[Dmarcoux111]

So first let me say, i really appreciate the work you guys do, i sincerely love this library. The different draw modes are things you should learn in an intro to GL graphics course. Learning from first principles is important to me, and there are edge cases ( like heightmaps ) where using different draw modes is more efficient, making knowing that stuff important right? What I am hearing is it was too tough to refactor a class ( Raycaster ) and its for some reason important to treat GLTF as special, so you removed a feature to move forward... which, I understand, just disagree.

[Dmarcoux111]

I dont buy the argument, 'some of our classes didnt work with different draw modes' so we NEED to remove them because we want all our classes to play together. ThreeJS is an abstraction for WebGL, it shouldnt limit ur ability to use webgl right? ( but im not the person maintaining all this so its easy for me to say rite? )

[Mugen87]

but im not the person maintaining all this so its easy for me to say rite

Correct.

[Dmarcoux111]

@Mugen87 Is there a way to use triangle strips that i dont know about tho ( i guess i can start making my own webgl classes )? I use this library to visualize massive imagery and elevation data sets, i can have 20gb images and even terabyte data sets, and saving memory really scales up as you get up there and is necessary. The thing that makes this a great library to me is u can do most things easily, and hard things with some effort.

[WestLangley]

I dont buy the argument, 'some of our classes didnt work with different draw modes' so we NEED to remove them because we want all our classes to play together. ThreeJS is an abstraction for WebGL, it shouldnt limit ur ability to use webgl right?

@Dmarcoux111 You are correct.

That being said, what is the minimum limited support that your need?

[Dmarcoux111]

@WestLangley Great question, I do my raycasting with the GPU in a shader ( just spit out position to a frame buffer and look up with mouse coords ), so really just an instruction to tell the GPU to connect my verts using GL_TRIANGLE_STRIP.

[Dmarcoux111]

Relevant code if it helps...

class Tile extends THREE.Mesh {
  constructor(
    geometry,
    material,
    heightmap,
    header,
    stats,
    offset,
    lod
  ) {
    super( geometry, material )
    this.header = header
    this.offset = offset
    this.lod = lod
    this.nodes = [];
    const length = 256 << lod;
    const mean = stats.mean;
    const center = new THREE.Vector3(
      this.header.translation.x + ( offset.x + length / 2 ) * this.header.scale.x,
      this.header.translation.y + ( offset.y + length / 2 ) * this.header.scale.y,
      mean * this.header.scale.z
    )
    const radius = Math.sqrt( length**2 + length**2 ) / 2;
    this.boundingSphere = new THREE.Sphere( center, radius )
    this.material.uniforms.scale = {
      type: 'f',
      value: 1 << lod,
    };
    this.material.uniforms.offset = {
      type: 'v2',
      value: offset,
    };
    this.material.uniforms.heightmap = {
      type: 't',
      value: heightmap,
    };
    this.material.uniforms.mvRTCMatrix = {
      type: 'm4',
      value: new THREE.Matrix4(),
    };
    this.drawMode = THREE.TriangleStripDrawMode
    this.frustumCulled = false
    this.visible = false
  }
  onBeforeRender() {
    let mv = new THREE.Matrix4();
    mv = mv.multiplyMatrices( window.CAMERA.matrixWorldInverse, this.matrixWorld )
    const origin = new THREE.Vector4(
      this.header.translation.x,
      this.header.translation.y,
      0.0,
      1.0
    );
    origin.applyMatrix4( mv );
    const mvRTCMatrix = new THREE.Matrix4().set(
    mv.elements[ 0 ], mv.elements[ 4 ], mv.elements[ 8 ], origin.x,
    mv.elements[ 1 ], mv.elements[ 5 ], mv.elements[ 9 ], origin.y,
    mv.elements[ 2 ], mv.elements[ 6 ], mv.elements[ 10 ], origin.z,
    mv.elements[ 3 ], mv.elements[ 7 ], mv.elements[ 11 ], mv.elements[ 15 ] )

    this.material.uniforms.mvRTCMatrix.value = mvRTCMatrix
  }
}

module.exports = Tile

Then the tile geometry:

    //  Geometry
    const positions = this.getPositions( 256 );
    const indices = this.getIndices( 256 );
    this.geometry.setAttribute( 'position', new THREE.BufferAttribute( positions, 3 ) );
    this.geometry.setIndex( new THREE.BufferAttribute( indices, 1 ) );

  getPositions( length ) {
    const positions = [];
    for ( let y = length; y >= 0; y-- ) {
      for ( let x = 0; x <= length; x++ ) {
        positions.push( x, y, 0 );
      }
    }
    return new Uint16Array( positions );
  }
  getIndices( length ) {
    const indices = [];
    for ( let j = 0; j < length; j++ ) {
      for ( let i = 0; i < length + 1; i++ ) {
        const triangle1 = j * ( length + 1 ) + i;
        const triangle2 = ( j + 1 ) * ( length + 1 ) + i;
        indices.push( triangle1 );
        indices.push( triangle2 );
        if ( i === length && j !== length - 1 ) {
          const degenerateTriangle = ( j + 1 ) * ( length + 1 ) + i;
          indices.push( degenerateTriangle );
        }
      }
      if ( j !== length - 1 ) {
        const degenerateTriangle = ( j + 1 ) * ( length + 1 );
        indices.push( degenerateTriangle );
      }
    }
    return new Uint32Array( indices );
  }

[Mugen87]

Supporting features and making a library maintainable is always a trade-off. Rendering triangle fan and strips are clearly edge cases to me. Triangle fans are not even recommended in WebGL 1. Although triangle strips are supported by glTF, I'm not aware of an exporter that actually produces it. Apart from that, I've seen it used sparsely in the past five years in WebGL in general.

Regarding the resulting over-engineering in the engine, I do vote to just support triangles.

[Dmarcoux111]

@Mugen87

Supporting features and making a library maintainable is always a trade-off. Rendering triangle fan and strips are clearly edge cases to me. Triangle fans are not even recommended in WebGL 1.

Totally agree.

Although triangle strips are supported by glTF, I'm not aware of an exporter that actually produces it.

Irrelevant unless the plan is to build the library around GLTF.

Apart from that, I've seen it used sparsely in the past five years in WebGL in general.

Totally agree

Regarding the resulting over-engineering in the engine, I do vote to just support triangles.

Is it over-engineering if you are making your engine less powerful? Sounds like you are pidgeon-holing the engine for GLTF

[Mugen87]

I'm not sure it's an official thing but keeping the engine align to glTF was definitely an influence factor in the past. E.g. #7290 (comment)

[donmccurdy]

glTF allows triangle strips, how is three.js not allowing triangle strips "pigeon-holing"?

@Dmarcoux111 that a feature exists in WebGL is not a sufficient argument. We maintainers have to deal with feature requests and bug reports or supposed bug reports (why does ____ not work?) that consume our time. Every time someone reports that raycasting doesn't work, or skinning is broken, we have to investigate why that is. Maintaining and debugging code paths for different draw modes cost us time and energy that could be spent on other things, and especially when features don't work in all cases, we get more bug reports.

If you'd like to share specific performance numbers about why triangle strips are really better for your application, that would be a better line of argument than saying we have to maintain abstractions for this just because it exists in WebGL.

[Dmarcoux111]

@donmccurdy

glTF allows triangle strips, how is three.js not allowing triangle strips "pigeon-holing"?

Because you are saying, we will make our decisions about what we render based on if it is glTF or not.

that a feature exists in WebGL is not a sufficient argument.

Fare enough, I guess I misunderstood the purpose of the library. I thought it was an abstraction for webGL.

We maintainers have to deal with feature requests and bug reports or supposed bug reports (why does ____ not work?) that consume our time. Every time someone reports that raycasting doesn't work, or skinning is broken, we have to investigate why that is. Maintaining and debugging code paths for different draw modes cost us time and energy that could be spent on other things, and especially when features don't work in all cases, we get more bug reports.

Totally understand, I maintain code for work.

If you'd like to share specific performance numbers about why triangle strips are really better for your application, that would be a better line of argument than saying we have to maintain abstractions for this just because it exists in WebGL.

My link got buried i guess, but here is the argument for Triangle Strips performance-wise: https://www.learnopengles.com/tag/index-buffer-object/

TLDR: Less vertices, single draw call.

*btw, I am not saying you NEED to do anything lol, you all are the maintainers and know way more about this than I do. My vote means nothing. I just want you all aware that this decision breaks a feature I was using. From the thread, you all seemed unsure if people actually use it in the wild for logical purposes. There is atleast one person lol

[Dmarcoux111]

@donmccurdy

glTF allows triangle strips, how is three.js not allowing triangle strips "pigeon-holing"?

Wait now I am confused... I assume glTF under the hood is buffer geometry?? How do you render gltf with triangle strips if you can't render buffer geometry with triangle strips?

[mrdoob]

@Dmarcoux111 Are those terrains you're visualizing a heightmap?

[Dmarcoux111]

@mrdoob yiss, specifically GeoTIFF, Digital Elevation Models, which can be gigantic, my test case one is 9gb I break them into quadtree tiles, where each tile shares a geometry, and takes one draw call, updating shaders, uniforms, etc. makes it so I have to save memory and draw calls wherever I can. Basically chunked LOD strategy with extra steps.

Chapter 14 of this book: https://www.virtualglobebook.com/ ( the software went on to become Cesium, actually a really good read! )

[WestLangley]

That being said, what is the minimum limited support that your need?

just an instruction to tell the GPU to connect my verts using GL_TRIANGLE_STRIP.

...So only the ability to render strips -- and you have your own loader and raycaster, correct?

This is not my decision to make, but I want to clarify your minimum requirement.

[Dmarcoux111]

@WestLangley Correct

[Dmarcoux111]

After a little thought, I think I am prioritizing a micro-optimization. I think it is probably better if I solve this on my end than you guys change the library. I am a bit skeptical if it is a good idea to remove functionality, but I DO value moving towards a standard like GLTF a bit more than saving some draw calls for a heightmap. Thanks for listening though, and again, really appreciate the work and this library!

[WestLangley]

I think I am prioritizing a micro-optimization

Oh. I thought you had already demonstrated a performance problem. :/

Next time, do that first, please.

[Dmarcoux111]

I get a slightly higher framerate ( like 5s ) moving around my scene with only doing 1 draw call, and save a bit of memory on the GPU, but that to me is a micro-optimization, I can make up for that somewhere else. Let me see if i can contrive an example for u using some open source images, may take a bit. But yes, one draw call is more performant than doing a draw call each strip when it comes to heightmaps, thats why that draw mode exists ( I think ).

https://www.learnopengles.com/tag/index-buffer-object/