2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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: sarielhp.org/p/01/fitting/fitting.pdf). $\endgroup$ – Sariel Har-Peled May 19 '16 at 1:28
1
$\begingroup$

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.

    1. 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).

$\endgroup$
1
$\begingroup$

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.

$\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.