<p>Before GPUs were popular we rendered without using Z-Buffers and instead used polygon sorting to make sure things were drawn back-to-front correctly. </p>

<p>By having a BSP with only convex geometry we guarantee that each leaf node will not have any ordering issues with the polygons contained in them, the BSP traversal algorithm itself can then produce a depth-sorted node list for you.</p>

<p>These days we have z-buffers so the need for convex leaf nodes isn't really that important, in some ways its better to render front-to-back also to take advantage of early-z optimisations on hardware.</p>

CC BY-SA 3.0
2017-10-06T05:25:48.573Z
2017-10-06T05:25:48.573Z
PaulHK
<p>Because with 2 non-overlapping convex polygons you can always say that 1 polygon is closer to a point than another.</p>

<p>If they are not convex then for example with a U surrounding a circle. You cannot say easily which should be drawn first.</p>

CC BY-SA 3.0
2017-10-05T15:18:08.323Z
2017-10-05T15:18:08.323Z
ratchet freak
<p>Well, BSP is an application of a Binary Search Tree (BST)</p>

<p>BSTs need a criterium to propagate the search through itself. Put simply, the criterium used in BSP is in which side of a partition a point is. Each partition just divides space in two parts. </p>

<p>It is absolutely imposible to create a concave polygon (or polyhedron) by dividing space in halves. I dare you to try, you will see that it cannot be done</p>

CC BY-SA 3.0
2017-10-05T22:07:55.657Z
2017-10-05T22:07:55.657Z
Sebastián Mestre
<p><a href="https://soulsphere.org/apocrypha/bsp/" rel="nofollow noreferrer">This</a> article says that binary space partitioning divides the map into convex polygons.</p>

<blockquote>
  <p>[...]<br>
  Before the map can be rendered we must perform a number of
  calculations on it. However, once these calculations are performed
  their results can be used many times. This is one of the advantages of
  BSP — once the calculations are performed they do not need to be done
  again, unless the map is changed. BSP only allows ”static” maps, or
  ones that do not move. If a map has any moving parts then they must be
  rendered separately.</p>
  
  <p>What must be done is to partition, or divide up, <strong>the map into convex
  polygons</strong>.</p>
</blockquote>

<p>Why should non-convex polygons be partitioned into convex polygons? Is there a mathematical basis behind this?</p>

<rendering>
Why do we have to partition non-convex polygons into convex polygons in a map in Binary Space Partitioning?
Sean Francis N. Ballais
# Why do we have to partition non-convex polygons into convex polygons in a map in Binary Space Partitioning?

(Asked by: username_0 on 2017-10-05)

[This](https://soulsphere.org/apocrypha/bsp/) article says that binary space partitioning divides the map into convex polygons.

> [...]  
> Before the map can be rendered we must perform a number of
> calculations on it. However, once these calculations are performed
> their results can be used many times. This is one of the advantages of
> BSP — once the calculations are performed they do not need to be done
> again, unless the map is changed. BSP only allows ”static” maps, or
> ones that do not move. If a map has any moving parts then they must be
> rendered separately.
>
> What must be done is to partition, or divide up, **the map into convex
> polygons**.

Why should non-convex polygons be partitioned into convex polygons? Is there a mathematical basis behind this?

**Tags:** rendering


---

## 3 answers

### Answer by username_1 on 2017-10-06. Score: 1 | Accepted answer

Before GPUs were popular we rendered without using Z-Buffers and instead used polygon sorting to make sure things were drawn back-to-front correctly.

By having a BSP with only convex geometry we guarantee that each leaf node will not have any ordering issues with the polygons contained in them, the BSP traversal algorithm itself can then produce a depth-sorted node list for you.

These days we have z-buffers so the need for convex leaf nodes isn't really that important, in some ways its better to render front-to-back also to take advantage of early-z optimisations on hardware.


---

### Answer by username_2 on 2017-10-05. Score: 3

Because with 2 non-overlapping convex polygons you can always say that 1 polygon is closer to a point than another.

If they are not convex then for example with a U surrounding a circle. You cannot say easily which should be drawn first.


---

### Answer by username_3 on 2017-10-05. Score: 1

Well, BSP is an application of a Binary Search Tree (BST)

BSTs need a criterium to propagate the search through itself. Put simply, the criterium used in BSP is in which side of a partition a point is. Each partition just divides space in two parts.

It is absolutely imposible to create a concave polygon (or polyhedron) by dividing space in halves. I dare you to try, you will see that it cannot be done


---

