1
$\begingroup$

This 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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.