PDA

View Full Version : Triangle: Circumscribed Circle



john_connor
05-16-2017, 05:40 AM
hi there,

library used: glm

lets say we have 3 arbitrary points A, B and C in 3D space, we dont know if and which are laying in a line or even if all of those are (0|0|0). the coords of these points are described in float (or double)

1. question:
whats the approch to calculate the point in 3D space that is the center if a circle which lays on these 3 points, the "circumscribed circle" center ?

in pure math (that is without bothering about floating-point precision etc), i'd:
middleAB = A + AB / 2
normal = cross(AB, AC)
tocenterAB = cross(normal, AB)

first line:
X = middleAB + n * tocenterAB

the same then for AC:
X = middleAC + n * tocenterAC

then intersect both lines. the problem is that the slightest precision loss will make these 2 lines not intersect. how to do it "the right way" ?


2. question:
lets say we have a bunch of points, we want to calculate the center M + radius R of the smallest sphere that contains all of these points:

case 1: 1 point --> R = 0, M = point
case 2: 2 points --> R = AB / 2, M = (A+B) / 2
case 3: 3 points --> ??? see question 1
case 4: 4 points --> ??? :doh:
case N: N points --> reduce to 4 points that are furthest away

the reason for that is that i want to calculate bounding spheres:

struct BoundingSphere {
vec3 Center; /* offset from "local space" */
float Radius = 0.0f;
};


3. question:
would you do that using a (vertex or compute) shader to do that for complex models ?

4. question:
having a model with bones, would you do this calculation at runtime (on the fly instead of once at initialization) ? each frame (possibly not) ? each few (500) milliseconds ? or just precalculate for each "pose" another bounding sphere and interpolate between those ?

i'm looking for a method to check for collision for arbitrary object, these models shouldnt have a "scaling" component so the they only have different translation / rotation component at each bone (if any available). lets say its for a flight simulator kind of game ...

last but not least: can i use glm to do anything of this ?

thanks for your suggestions !

GClements
05-16-2017, 05:02 PM
For 1, I'd use this formulation (https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_from_cr oss-_and_dot-products), as it doesn't introduce any unnecessary failure modes (if an edge is degenerate or two edges are parallel, then the problem is ill-defined).

For the others: it's unlikely to be worth the effort of calculating the exact (minimal) bounding sphere, particularly when the sphere is itself only an approximation to the collision volume.