"Name" of this 3D modeling problem


Context / existing app

I am currently building an editor to shape the geometry of one single closed volume (a closed model of a room for acoustic calculations).

The user starts by drawing the floor and entering a height to extrude the 3D room.

I think that’s a fast and easy way to get a first rough geometry and it works already.

Looks like this now:

What I try to add

I am currently starting to work on the second step. I want the user to be able to change the shape of that 3D model to add details like slanted ceiling etc. I always want the mesh to be valid for the acoustic calculations (closed, no crossings,…). So I don’t want the user to move a point, the mesh opens up, the user draws a line to close the mesh again. Instead I want to only add those features where I can provide automatic detection of what is needed to keep the mesh closed.

I played around with Sketchup today to get inspiration. When I move up one point of a box, sketchup automatically adds a necessary edge.
image image
It could have added the other diagonal like this (but it didn’t in that case). I shaped this manually to show you what I mean.

Interestingly it decides differently in this case
image image
It could have done it like this

My question

Is there a name for this type of problem? I don’t find the right wording to make google or this forum come up with examples, discussions, algorithms…
Any idea where to get inspiration for solving those different cases?


beautiful triangulation
also topology but that will just lead to character modeling
You need to find old papers on the topic

fyi your question unlocked a tech term I WAS trying to recall for a separate thing. Convex Hull!!!

1 Like

The problem oscillates around the terms planar and triangulation.

It is a combination of several phenomena:

  • in computer graphics almost always faces of 3D objects are triangles (yes, there are exceptions to this, but when the model goes down the the GPU, it is only a soup of triangles, lines and points)
  • if you see a square, most likely it is two triangles, but the shared edge is not visible (or rendered), so it appears as one shape
  • in computer graphics faces should always be planar – otherwise you will open a Pandora’s box

The result of these 3 things is:

  • when you move one vertex of a square, the square is not planar any more, and you can see the two triangles that made it
  • if you want the bend the square along the other diagonal, then you should change the triangulation of the square (i.s. how it is split into triangles)
  • alternatively you should employ a more complex algorithm that will preserve all faces planar, e.g. you change one vertex and some other vertices are also changed
1 Like

Thanks a lot for your very intersting and helpful answers!!

I have decided earlier, that I don’t use one BufferGeometry to render this one closed volume. Instead I add one mesh per coplanar polygon (wall) and one line mesh to emphasize the edges. I think, that this simplifies things like selecting walls and edges and I guess that the performance difference will be not that big.

But because of this I think in “walls”, not in “triangles”. I guess if I would have decided for the one BufferGeometry approach, I immediately would have thought about the existing triangles. And sketchup does exactly that I guess.

I already use ShapeUtils.triangulateShape to build the BufferGeometries that I use for rendering the planar polygons / walls. I guess I will try the following now (when a point is moved):

  • for alle walls the point is part of, check if the wall is still planar
  • for all walls that are not planar anymore, read the points/triangles in its BufferGeometry and split into two BufferGeometries adding one Line Mesh at the new edge

I use a graph datastructure to know which walls/edges/points exist and how they are connected. So I should be able to find what I need.

Please let me know if that sounds more complicated than necessary to you :slight_smile:

why are you making more than one buffer geometry?!?!?!
You need to think about this as array sorting. Constantly building geos is gonna eat performance. And you have to fuze them make together

Walls are triangles thats just the truth. You could instead think of them as N-Gons Tris, Quads & N-Gons | 3D Modeling Resources

Anyway, anything that works is fine though. Just where you put the logic order and then handling export for overlapping vertices

1 Like

so to sum up, you throw an incomplete task at the black box algo and like its result in one case, but dislike it in another case.

Is there a name for this type of problem?

human nature? when you don’t know what you want until you see it. otherwise you would get the exact result you needed, by triangulating and rotating the edges in advance.

My understanding about my two possibilites

  • separate meshes with own materials that I can for example color on mouse over etc
  • one custom BufferGeometry where things like mouseover over parts of it are more tricky but rendering performance is better

I don’t have lots of knowhow in 3D/threejs but my architectural gut feeling tells me that I should write most of my code within my layer of abstraction of walls. In threejs terms: having a custom WallGeometry feels better than a custom RoomGeometry. I can be wrong here. But as I think that the models will not get very complex (usually tens of walls, not hundreds or thousands) I don’t want to sacrifice code-understandability for performance. Of course, if you see other advantages, having one BufferGeometry, or think that rendering performance will not allow ~50walls, I should of course rethink this approach. Do you?

An image of the current state to not be too abstract.
When you mouse over an edge a new box spawns under your cursor. You can play around with the 2D version of this behavior here.

I am not sure what you mean with “constantly”. My plan is to only build new geometries if the user moves a point in a way where it is not planar anymore with the other points in one of its WallGeometries. As the wall is potentially not convex it is also possible that re-triangulation is necessary but I guess this is also true if I only use one RoomGeometry.

Sorry @makc3d, I am not sure I understand your point.
With “you” you mean the user, right? I, as a user, move a point and something will happen, but maybe not what I meant. I as a user have to work to do it right.
I absoultely agree but at the same time I as a developer have a focus on usability and am willing to work a bit harder and get more complex code when this leads to easier usage. To be able to do that I ask for “words” as I was not even able to search for existing literature, algorithms, etc. It’s getting better :wink:

my point is, that if you can properly explain why one edge is preferable versus another, you can express this as a code to create said edges. if you dont know what you want (or what your user will want) then you cant make such an algo, and your only choice is to do what sketchup or blender do - create whatever edge, and let the user rotate it later if they do not like it.