Skip to main content
4 of 4
added 123 characters in body

Finding a bounding volume (line segments) from a kDop definition.

I have a problem. I'm trying to recover a bounding volume (actually line segments that form the bounding volume) from a kDop definition (in a 3D space). (its to draw the kDop on screen)

In my kDOP structure i have the Min/Max values calculated for each axis. (And well, i know the axis used)

I tried before coming here 3 ways to resolve it :

  1. Intersecting 3 neighboring planes to find a point and then connecting them (Sometimes the intersection is out of the k-DOP, i didn't manage to find a way to figure the correct planes to use)

  2. Starting from the lines of the AABB (DOP6) and then intersecting the lines with each of the k-DOP planes, but when a line is completely behind a plane (i.e. not visible), we have to add two or more new lines and i don't know which is to be drawed and which not. :P (and i get too many lines drawed)

  3. Brute force method. Intersect each plane with each other plane to get a set of lines and then intersect these lines with each plane to find the correct line segment (or discard the line) (too slow :()

What's the best way to go? Can you give some explanation on it?

Thanks

EDIT : About the slowness. Well yes, i need to do it for 100-120 objects under 16,667 ms (n^3 method takes 0,96 ms (and i've optimized pretty much everything))

EDIT 2: Answering the questions from TonyK :

  1. (1,0,0)(0,1,0)(0,0,1) // AABB (Axis Aligned Bounding Box)

    (1,1,1)(1,-1,1)(1,1,-1)(1,-1,-1) // Corners

    (1,1,0)(1,0,1),(0,1,1),(1,-1,0),(1,0,-1),(0,1,-1) // Edges

These are the axes used. Are fixed and I can happen to use a subset of those. (only AABB (DOP6) or AABB + Corners (DOP14) or AABB+Corners+Edges (DOP26)). Yes, the only thing changing is the Min/Max values. (The normals for each plane are prestored (26 normals in the worst case (DOP26)))

  1. My point of view is the camera of the simulation and "can" change. (the line segment obtained will be multiplied by World/View/Projection matrix to get the final position on the Viewport, but that's a GPU detail)

  2. Mhn...well, there are Axes that do not intersect each other.

  3. What do you mean by "treating the bounding plane as opaque"?

EDIT 3:

Regarding the other question, No, I treat them as wireframe so the lines under the kDOP surface will appear.