Major Steps
If a (triangular) face f belongs to a particular spherical part, then with a very high probability, the faces adjacent to f would also be co-spheric with f.We estimate the parameters of the sphere, which all the adjacent faces potentially belong to. The algorithm SPReAD considers the discrete points along the circum-normals of these faces as input, and finds the approximate center.
The first face f is selected at random. Although there exists a unique circle passing through the three vertices of any triangle, there exists an infinitude of spheres passing through them. The centers of all these spheres are collinear in 3D space. Hence, for a given face f with a center point taken on its circum-normal, the sphere parameters are first obtained, and then we build the initial spherical part on it by considering its three adjacent triangles to obtain the common solution space of these four triangles. The larger spherical part is built from this by doing a breadth-first search iteratively on the set of faces adjacent to each other whose corresponding ε-balls in the parameter space have all pair-wise intersection.
The parameter space has four dimensions, the first three being corresponding to the three coordinates of the object space and the fourth to the radius. The distance metric used by us in this parameter space is based on L2-norm. If pi be the point in the 4D parameter space corresponding to a sphere Si passing through the vertices of a face f, then the ε-ball corresponding to Si is denoted by φ(pi,ε) and defined as the 4D hyper-sphere with center at pi and radius ε. If Si has center ci(xi,yi,zi ) and radius ri, then it is uniquely represented in the parameter space by the point pi(ci,ri). Hence, two faces fi (with circum-normal Ni) and fj (with circum-normal Nj) are said to be co-spheric with each other if and only if there exist two points pi(ai,ri) and pj(aj,rj) in the parameter space such that ai∈Ni, aj∈Nj, and there exists a non-empty intersection between φ(pi,ε) and φ(pj,ε). Evidently, two ε-balls are said to intersect each other if and only if the distance between their centers does not exceed 2ε. In general, a set of faces are mutually co-spheric if the two ε-balls corresponding to some axial point of one and some axial point of the other in each pair from the set have a non-empty intersection in the 4D parameter space. The proposed algorithm SPReAD is made flexible to suit the needs of different objects by providing the hyper-ball radius, ε. The value of ε is specified w.r.t. the normalized scale, and varies from 0.01 to 0.04, as shown in the paper. Smaller the value of ε, tighter is the detection of spherical parts, and larger the value of ε, looser is the detection. The speed and precision of the algorithm is decided by another parameter, namely N, which indicates the number of discrete points to be considered along the circum-normal of each triangle while detecting a spherical part.
|
|
|
|
Information in DCEL. The red triangle denotes a face f having three
(directed) edges, shown in blue. Each of of three edges is defined by a pair of vertices
(blue), and has a twin edge in its adjacent face (yellow).
The unit normals are computed from the edges corresponding to the faces. |
Finding the center of the sphere built by a face f (shown in red) and its three adjacent faces {f1, f2, f3} (yellow), using axial discretization of their circum-normals (N, N1, N2, N3). |
