<p>Just lift the points to higher dimensions, and use BSP in the higher dimensional space. This is a standard techniuqe - see linearization (in section 3 here: <a href="http://sarielhp.org/p/04/survey/survey.pdf" rel="nofollow">http://sarielhp.org/p/04/survey/survey.pdf</a>). For example, you map a point $(x,y)$ to the 3d point $(x,y,x^2+y^2)$. This lifts the points to a paraboloid in 3d. Now, any 3d plane corresponds a circle/line in the original plane. Thus, building the BSP on the lifted points, would correspond to hierarchial partition with circles and lines.</p>

<p>Of course, this might completely ruin the query process on the points which you might try doing with the BSP.</p>

CC BY-SA 3.0
2016-06-20T15:23:27.857Z
2016-06-20T15:23:27.857Z
Sariel Har-Peled
<p>You can absolutely do it with kernelized support vectors.  I don't have a publication handy but I've implemented it myself before.  You'll probably want to use quadrics for the split planes, and unfortunately I only found a suboptimal way to do csg (Naylor's original bsp/csg algorithm from 1990); there may be a better way.  But it's very possible, and allows for a couple really interesting things:</p>

<ol>
<li><p>ray segment/quadric bsp intersection tests can be done extremely effectively with the following procedure: first, early exit if the two points are not in the same node, then ray-march using the signed distance from the nearest quadric hyperplane, which is easy to compute by traversing the tree.  This becomes very efficient, especially for certain smoother shapes, because the trees tend to be very shallow.</p></li>
<li><p>you can fit the hyperplanes to a sampling of a signed distance function by using linear least squares.  Recursively split until all sample points are in the same node of the tree and the mean square error of the signed distance to the shape is below a certain tolerable level, at each stage using least squares to optimize the coefficients of the quadric split.</p>

<ol start="3">
<li>as implied in (1), determining whether one point is accessible from another reduces to determining whether they are in the same node of a very shallow tree, useful for 3d blob detection and such.</li>
</ol></li>
</ol>

<p>As far as the implementation, it really is simple, as you have hinted.  Just use a few more coefficients in the hyperplanar equation for each node, and the rest will flow.   But if you want to look at my implementation, it's somewhere buried in my github (vpostman).</p>

CC BY-SA 3.0
2016-05-18T20:21:50.233Z
2016-05-18T20:21:50.233Z
Kevin Daley
<p>Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily known/calculated continuous subset of it to the points on the surface at every branch. Let's furthermore say that I wanted those surfaces to be curved.</p>

<p>I could arbitrarily approximate curved partitioning surfaces by using a helluva lot of straight planes ala the classic BSP, but that seems silly.</p>

<p>Is there prior art in using NURBS or kernelized support vectors or <em>whatever</em> to define smooth curved surfaces in a binary space partitioning tree s.t. extraction of some of the boundaries' points from the representation (enough to illustrate the boundary) is easily (and preferably deterministically, avoiding monte carlo methods) accomplished? Or is this one of those trivial knowledge-synthesis problems and I'm better off just winging it? If not, could someone please point me in the right direction?</p>

CC BY-SA 3.0
2016-05-19T01:28:56.593Z
Life the point set to an appropriate manifold in higher dimension and do BSP in this space. The advantage is that you are dealing with hyperplanes in this lifted space. for example, if you wanted to use lines and circles, you would map a point $(x,y)$ to the lifted point $(x,y,x^2 + y^2)$. This is a standard trick in computational geometry (it is called lienarization - see here from relevant refs:  http://sarielhp.org/p/01/fitting/fitting.pdf).
Sariel Har-Peled
<cg.comp-geom><binary-space-partitions>
BSP, but with curved surfaces (NURBS? kernelized support vectors?)
user
# BSP, but with curved surfaces (NURBS? kernelized support vectors?)

(Asked by: username_0 on 2014-04-14)

Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily known/calculated continuous subset of it to the points on the surface at every branch. Let's furthermore say that I wanted those surfaces to be curved.

I could arbitrarily approximate curved partitioning surfaces by using a helluva lot of straight planes ala the classic BSP, but that seems silly.

Is there prior art in using NURBS or kernelized support vectors or *whatever* to define smooth curved surfaces in a binary space partitioning tree s.t. extraction of some of the boundaries' points from the representation (enough to illustrate the boundary) is easily (and preferably deterministically, avoiding monte carlo methods) accomplished? Or is this one of those trivial knowledge-synthesis problems and I'm better off just winging it? If not, could someone please point me in the right direction?

**Tags:** cg.comp-geom, binary-space-partitions

> **Comments:**
> **username_1**: Life the point set to an appropriate manifold in higher dimension and do BSP in this space. The advantage is that you are dealing with hyperplanes in this lifted space. for example, if you wanted to use lines and circles, you would map a point $(x,y)$ to the lifted point $(x,y,x^2 + y^2)$. This is a standard trick in computational geometry (it is called lienarization - see here from relevant refs:  http://sarielhp.org/p/01/fitting/fitting.pdf).  

---

## 2 answers

### Answer by username_1 on 2016-06-20. Score: 1

Just lift the points to higher dimensions, and use BSP in the higher dimensional space. This is a standard techniuqe - see linearization (in section 3 here: <http://sarielhp.org/p/04/survey/survey.pdf>). For example, you map a point $(x,y)$ to the 3d point $(x,y,x^2+y^2)$. This lifts the points to a paraboloid in 3d. Now, any 3d plane corresponds a circle/line in the original plane. Thus, building the BSP on the lifted points, would correspond to hierarchial partition with circles and lines.

Of course, this might completely ruin the query process on the points which you might try doing with the BSP.


---

### Answer by username_2 on 2016-05-18. Score: 1

You can absolutely do it with kernelized support vectors. I don't have a publication handy but I've implemented it myself before. You'll probably want to use quadrics for the split planes, and unfortunately I only found a suboptimal way to do csg (Naylor's original bsp/csg algorithm from 1990); there may be a better way. But it's very possible, and allows for a couple really interesting things:

1. ray segment/quadric bsp intersection tests can be done extremely effectively with the following procedure: first, early exit if the two points are not in the same node, then ray-march using the signed distance from the nearest quadric hyperplane, which is easy to compute by traversing the tree. This becomes very efficient, especially for certain smoother shapes, because the trees tend to be very shallow.
2. you can fit the hyperplanes to a sampling of a signed distance function by using linear least squares. Recursively split until all sample points are in the same node of the tree and the mean square error of the signed distance to the shape is below a certain tolerable level, at each stage using least squares to optimize the coefficients of the quadric split.

   3. as implied in (1), determining whether one point is accessible from another reduces to determining whether they are in the same node of a very shallow tree, useful for 3d blob detection and such.

As far as the implementation, it really is simple, as you have hinted. Just use a few more coefficients in the hyperplanar equation for each node, and the rest will flow. But if you want to look at my implementation, it's somewhere buried in my github (vpostman).


---

