<p>As a little project, I'd like to implement a BSP merging algorithm for Boolean operations on solids. But to even tell whether it works, I need some way to render the BSP tree. In other words, I have a BSP tree corresponding to some 3D solid, with all its leaves having an indicator value of "0" or "1", and I'd like to render out the areas corresponding to the leaves with value 1.</p>

<p>I understand the general approach for doing the actual BSP tree merging, but I'm not really sure how to render a BSP tree. I'm not interested in efficiency, and I don't need to convert the BSP tree to an actual mesh/boundary representation - I just want to render the BSP tree somehow (as simply as possible), to have an idea whether the implementation works.</p>

<p>I'd guess that one way to do this would be to go through the tree, and somehow progressively clip the space I have. So I might start with some sort of very large cube (that corresponds to the full 3D space), and I keep clipping it by half planes as  I go through the tree. If I reach a leaf with value 1, I "save" the mesh and render it. This might work, but it seems like a bit too much work, and honestly I'm not experienced in computer graphics, so I'd prefer if there was some easier way.</p>

<p>I'd appreciate any advice.</p>

CC BY-SA 4.0
2019-12-30T14:03:57.483Z
It doesn't sound like your BSP tree is correct for CSG operations. BSP tree's for CSG should have nodes which contain at least half space information (position and normal) or ideally a triangle (to check for coplanar cases), either original triangle of the BSP'ed mesh, or the split triangle as a result of spliting when an original mesh triangle straddles the plane/halfspace of another node. Inside/Outside is deduced by following the nodes inside/outside children, or splitting when straddling and putting back through the tree. No inside child node means triangle is inside and vice versa.
lfgtm
CC BY-SA 4.0
2019-12-30T14:04:16.663Z
If you do this, you will have a new mesh within the tree (each node has a triangle) and this is easy to visualise. See here for an example of BSP CSG in C++ https://github.com/spiroyster/qdcsg/blob/master/qdcsg.hpp
lfgtm
CC BY-SA 4.0
2020-01-04T20:09:02.580Z
@lfgtm Thanks for the comment and sorry about a late answer, I was sick.

I don't understand what you mean with the triangle for a coplanar case. My nodes will just contain a point and normal to specify the plane. I also don't understand why you mention inside/outside deduction. Like I wrote in OP, I get how to do the merge - I'm not sure how to actually render the resulting tree. This doesn't really have anything to do with CSG operations - I was just hoping there might be an easier way to render the resulting tree, but I guess I'll just implement a mesh-slicing function in the end.
John P
CC BY-SA 4.0
2020-01-05T21:50:03.617Z
If not CSG (https://en.wikipedia.org/wiki/Constructive_solid_geometry), What do you mean by boolean operations on solids?
lfgtm
CC BY-SA 4.0
2020-01-06T18:06:40.863Z
I mentioned CSG for context, because it's basically the topic. For example however, I'm not really worried about starting with 2 meshes - I'm completely ignoring the fact of converting a mesh to a BSP. I'm starting with two BSP trees, I merge them, and I display the result.

In essence when doing CSG with BSP trees the problem can be split into:
1, Convert meshes to BSP trees.
2, Merge trees with the desired operation.
3, Convert resulting BSP tree back to a mesh.

What I'm essentially trying to do, is 3, in easiest possible way, or even skip it and just "render" the resulting tree.
John P
CC BY-SA 4.0
2020-01-06T18:12:53.000Z
Just out of curiosity, would you mind expanding on why you use the triangle for the plane representation and what you mean by the co-planar case? I don't understand how using a triangle helps compared to just using a plane. Numerical robustness?
John P
<rendering><3d><algorithm><computational-geometry>
BSP tree rendering
John P
# BSP tree rendering

(Asked by: username_0 on 2019-12-29)

As a little project, I'd like to implement a BSP merging algorithm for Boolean operations on solids. But to even tell whether it works, I need some way to render the BSP tree. In other words, I have a BSP tree corresponding to some 3D solid, with all its leaves having an indicator value of "0" or "1", and I'd like to render out the areas corresponding to the leaves with value 1.

I understand the general approach for doing the actual BSP tree merging, but I'm not really sure how to render a BSP tree. I'm not interested in efficiency, and I don't need to convert the BSP tree to an actual mesh/boundary representation - I just want to render the BSP tree somehow (as simply as possible), to have an idea whether the implementation works.

I'd guess that one way to do this would be to go through the tree, and somehow progressively clip the space I have. So I might start with some sort of very large cube (that corresponds to the full 3D space), and I keep clipping it by half planes as I go through the tree. If I reach a leaf with value 1, I "save" the mesh and render it. This might work, but it seems like a bit too much work, and honestly I'm not experienced in computer graphics, so I'd prefer if there was some easier way.

I'd appreciate any advice.

**Tags:** rendering, 3d, algorithm, computational-geometry

> **Comments:**
> **username_1**: It doesn't sound like your BSP tree is correct for CSG operations. BSP tree's for CSG should have nodes which contain at least half space information (position and normal) or ideally a triangle (to check for coplanar cases), either original triangle of the BSP'ed mesh, or the split triangle as a result of spliting when an original mesh triangle straddles the plane/halfspace of another node. Inside/Outside is deduced by following the nodes inside/outside children, or splitting when straddling and putting back through the tree. No inside child node means triangle is inside and vice versa.  
> **username_1**: If you do this, you will have a new mesh within the tree (each node has a triangle) and this is easy to visualise. See here for an example of BSP CSG in C++ https://github.com/spiroyster/qdcsg/blob/master/qdcsg.hpp  
> **username_0**: @username_1 Thanks for the comment and sorry about a late answer, I was sick.  I don't understand what you mean with the triangle for a coplanar case. My nodes will just contain a point and normal to specify the plane. I also don't understand why you mention inside/outside deduction. Like I wrote in OP, I get how to do the merge - I'm not sure how to actually render the resulting tree. This doesn't really have anything to do with CSG operations - I was just hoping there might be an easier way to render the resulting tree, but I guess I'll just implement a mesh-slicing function in the end.  
> **username_1**: If not CSG (https://en.wikipedia.org/wiki/Constructive_solid_geometry), What do you mean by boolean operations on solids?  
> **username_0**: I mentioned CSG for context, because it's basically the topic. For example however, I'm not really worried about starting with 2 meshes - I'm completely ignoring the fact of converting a mesh to a BSP. I'm starting with two BSP trees, I merge them, and I display the result.  In essence when doing CSG with BSP trees the problem can be split into: 1, Convert meshes to BSP trees. 2, Merge trees with the desired operation. 3, Convert resulting BSP tree back to a mesh.  What I'm essentially trying to do, is 3, in easiest possible way, or even skip it and just "render" the resulting tree.  
> **username_0**: Just out of curiosity, would you mind expanding on why you use the triangle for the plane representation and what you mean by the co-planar case? I don't understand how using a triangle helps compared to just using a plane. Numerical robustness?  

---

## 0 answers

