[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [38864] trunk/blender/source/blender/ blenkernel: Imported bsphere.c, mostly ifdef'd out for now
Nicholas Bishop
nicholasbishop at gmail.com
Sun Jul 31 04:03:40 CEST 2011
Revision: 38864
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=38864
Author: nicholasbishop
Date: 2011-07-31 02:03:39 +0000 (Sun, 31 Jul 2011)
Log Message:
-----------
Imported bsphere.c, mostly ifdef'd out for now
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/CMakeLists.txt
trunk/blender/source/blender/blenkernel/intern/customdata.c
Added Paths:
-----------
trunk/blender/source/blender/blenkernel/intern/bsphere.c
Modified: trunk/blender/source/blender/blenkernel/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/blenkernel/CMakeLists.txt 2011-07-31 02:03:33 UTC (rev 38863)
+++ trunk/blender/source/blender/blenkernel/CMakeLists.txt 2011-07-31 02:03:39 UTC (rev 38864)
@@ -81,6 +81,7 @@
intern/boids.c
intern/booleanops_mesh.c
intern/brush.c
+ intern/bsphere.c
intern/bullet.c
intern/bvhutils.c
intern/cdderivedmesh.c
Added: trunk/blender/source/blender/blenkernel/intern/bsphere.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/bsphere.c (rev 0)
+++ trunk/blender/source/blender/blenkernel/intern/bsphere.c 2011-07-31 02:03:39 UTC (rev 38864)
@@ -0,0 +1,1178 @@
+/*
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2011 by Nicholas Bishop
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_modifier_types.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_heap.h"
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+
+#include "BKE_cdderivedmesh.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_global.h"
+#include "BKE_library.h"
+#include "BKE_main.h"
+#include "BKE_subsurf.h"
+
+#include <assert.h>
+
+typedef struct Tri {
+ struct Tri *next, *prev;
+ unsigned int v[3];
+ float no[3];
+ float area;
+ int marked;
+} Tri;
+
+typedef struct Edge {
+ struct Edge *next, *prev;
+ unsigned int v[2];
+ Tri *tri[2];
+} Edge;
+
+/* note: a `frame' is four vertices (contiguous within the MVert
+ array), stored simply as the index of the first vertex */
+
+static void create_frame(float frame[4][3], const float co[3], float radius,
+ const float mat[3][3], float x_offset)
+{
+ float rx[3], ry[3], rz[3];
+ int i;
+
+ mul_v3_v3fl(ry, mat[1], radius);
+ mul_v3_v3fl(rz, mat[2], radius);
+
+ add_v3_v3v3(frame[3], co, ry);
+ add_v3_v3v3(frame[3], frame[3], rz);
+
+ sub_v3_v3v3(frame[2], co, ry);
+ add_v3_v3v3(frame[2], frame[2], rz);
+
+ sub_v3_v3v3(frame[1], co, ry);
+ sub_v3_v3v3(frame[1], frame[1], rz);
+
+ add_v3_v3v3(frame[0], co, ry);
+ sub_v3_v3v3(frame[0], frame[0], rz);
+
+ mul_v3_v3fl(rx, mat[0], x_offset);
+ for(i = 0; i < 4; i++)
+ add_v3_v3v3(frame[i], frame[i], rx);
+}
+
+static void create_mid_frame(float frame[4][3],
+ const float co1[3], const float co2[3],
+ const SkinNode *n1, const SkinNode *n2,
+ const float mat[3][3])
+{
+ create_frame(frame, co1, (n1->radius + n2->radius) / 2,
+ mat, len_v3v3(co1, co2) / 2);
+}
+
+static void add_face(MFace *mface, int *totface,
+ int v1, int v2, int v3, int v4)
+{
+ MFace *f;
+
+ f = &mface[*totface];
+ f->v1 = v1;
+ f->v2 = v2;
+ f->v3 = v3;
+ f->v4 = v4 == -1 ? 0 : v4;
+ if(!v4) {
+ f->v1 = v3;
+ f->v2 = v4;
+ f->v3 = v1;
+ f->v4 = v2;
+ }
+ (*totface)++;
+}
+
+static void connect_frames(MFace *mface, int *totface, int frame1, int frame2)
+{
+ int i;
+
+ for(i = 0; i < 4; i++) {
+ add_face(mface, totface,
+ frame2 + i,
+ frame2 + (i+1) % 4,
+ frame1 + (i+1) % 4,
+ frame1 + i);
+ }
+}
+
+static Tri *add_triangle(ListBase *tris, MVert *mvert, int v1, int v2, int v3)
+{
+ Tri *t;
+
+ t = MEM_callocN(sizeof(Tri), "add_triangle.tri");
+ t->v[0] = v1;
+ t->v[1] = v2;
+ t->v[2] = v3;
+ BLI_addtail(tris, t);
+
+ normal_tri_v3(t->no, mvert[t->v[0]].co, mvert[t->v[1]].co, mvert[t->v[2]].co);
+ t->area = area_tri_v3(mvert[t->v[0]].co, mvert[t->v[1]].co, mvert[t->v[2]].co);
+
+ return t;
+}
+
+static int point_tri_side(const Tri *t, MVert *mvert, int v)
+{
+ float p[3], d;
+ sub_v3_v3v3(p, mvert[v].co, mvert[t->v[0]].co);
+ d = dot_v3v3(t->no, p);
+ if(d < 0) return -1;
+ else if(d > 0) return 1;
+ else return 0;
+}
+
+static int mark_v_outside_tris(ListBase *tris, MVert *mvert, int v)
+{
+ Tri *t;
+ int outside = 0;
+
+ /* probably there's a much better way to do this */
+ for(t = tris->first; t; t = t->next) {
+ if((t->marked = point_tri_side(t, mvert, v) > 0))
+ outside = 1;
+ }
+ return outside;
+}
+
+static int edge_match(int e1_0, int e1_1, const unsigned int e2[2])
+{
+ /* XXX: maybe isn't necesseary to check both directions? */
+ return (e1_0 == e2[0] && e1_1 == e2[1]) ||
+ (e1_0 == e2[1] && e1_1 == e2[0]);
+}
+
+/* returns true if the edge (e1, e2) is already in edges; that edge is
+ deleted here as well. if not found just returns 0 */
+static int check_for_dup(ListBase *edges, unsigned int e1, unsigned int e2)
+{
+ Edge *e, *next;
+
+ for(e = edges->first; e; e = next) {
+ next = e->next;
+
+ if(edge_match(e1, e2, e->v)) {
+ /* remove the interior edge */
+ BLI_freelinkN(edges, e);
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+static void expand_boundary_edges(ListBase *edges, Tri *t)
+{
+ Edge *new;
+ int i;
+
+ /* insert each triangle edge into the boundary list; if any of
+ its edges are already in there, remove the edge entirely */
+ for(i = 0; i < 3; i++) {
+ if(!check_for_dup(edges, t->v[i], t->v[(i+1)%3])) {
+ new = MEM_callocN(sizeof(Edge), "Edge");
+ new->v[0] = t->v[i];
+ new->v[1] = t->v[(i+1)%3];
+ BLI_addtail(edges, new);
+ }
+ }
+}
+
+static int tri_matches_frame(const Tri *t, int frame)
+{
+ int i, j, match = 0;
+ for(i = 0; i < 3; i++) {
+ for(j = 0; j < 4; j++) {
+ if(t->v[i] == frame + j) {
+ match++;
+ if(match >= 3)
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+static void quad_from_tris(const Edge *e, int ndx[4])
+{
+ int i, j, opp = -1;
+
+ /* find what the second tri has that the first doesn't */
+ for(i = 0; i < 3; i++) {
+ if(e->tri[1]->v[i] != e->tri[0]->v[0] &&
+ e->tri[1]->v[i] != e->tri[0]->v[1] &&
+ e->tri[1]->v[i] != e->tri[0]->v[2]) {
+ opp = e->tri[1]->v[i];
+ break;
+ }
+ }
+ assert(opp != -1);
+
+ for(i = 0, j = 0; i < 3; i++, j++) {
+ ndx[j] = e->tri[0]->v[i];
+ /* when the triangle edge cuts across our quad-to-be,
+ throw in the second triangle's vertex */
+ if((e->tri[0]->v[i] == e->v[0] || e->tri[0]->v[i] == e->v[1]) &&
+ (e->tri[0]->v[(i+1)%3] == e->v[0] || e->tri[0]->v[(i+1)%3] == e->v[1])) {
+ j++;
+ ndx[j] = opp;
+ }
+ }
+}
+
+static void add_quad_from_tris(MFace *mface, int *totface, const Edge *e)
+{
+ int ndx[4];
+
+ quad_from_tris(e, ndx);
+
+ add_face(mface, totface, ndx[0], ndx[1], ndx[2], ndx[3]);
+}
+
+static GHash *calc_edges(ListBase *tris)
+{
+ GHash *adj;
+ ListBase *edges;
+ Edge *e;
+ Tri *t;
+ int i, e1, e2;
+
+ /* XXX: vertex range might be a little funky? so using a
+ hash here */
+ adj = BLI_ghash_new(BLI_ghashutil_inthash,
+ BLI_ghashutil_intcmp,
+ "calc_edges adj");
+
+ for(t = tris->first; t; t = t->next) {
+ for(i = 0; i < 3; i++) {
+ e1 = t->v[i];
+ e2 = t->v[(i+1)%3];
+ assert(e1 != e2);
+ if(e1 > e2)
+ SWAP(int, e1, e2);
+
+ edges = BLI_ghash_lookup(adj, SET_INT_IN_POINTER(e1));
+ if(!edges) {
+ edges = MEM_callocN(sizeof(ListBase),
+ "calc_edges ListBase");
+ BLI_ghash_insert(adj, SET_INT_IN_POINTER(e1), edges);
+ }
+
+ /* find the edge in the adjacency list */
+ for(e = edges->first; e; e = e->next) {
+ assert(e->v[0] == e1);
+ if(e->v[1] == e2)
+ break;
+ }
+
+ /* if not found, create the edge */
+ if(!e) {
+ e = MEM_callocN(sizeof(Edge), "calc_edges Edge");
+ e->v[0] = e1;
+ e->v[1] = e2;
+ BLI_addtail(edges, e);
+ }
+
+ /* should never be more than two faces
+ attached to an edge here */
+ assert(!e->tri[0] || !e->tri[1]);
+
+ if(!e->tri[0])
+ e->tri[0] = t;
+ else if(!e->tri[1])
+ e->tri[1] = t;
+ }
+ }
+
+ return adj;
+}
+
+static int is_quad_symmetric(const MVert *mvert, const Edge *e)
+{
+ int ndx[4];
+ float a[3];
+
+ quad_from_tris(e, ndx);
+
+ copy_v3_v3(a, mvert[ndx[0]].co);
+ a[0] = -a[0];
+
+ if(len_v3v3(a, mvert[ndx[1]].co) < FLT_EPSILON) {
+ copy_v3_v3(a, mvert[ndx[2]].co);
+ a[0] = -a[0];
+ if(len_v3v3(a, mvert[ndx[3]].co) < FLT_EPSILON)
+ return 1;
+ }
+ else if(len_v3v3(a, mvert[ndx[3]].co) < FLT_EPSILON) {
+ copy_v3_v3(a, mvert[ndx[2]].co);
+ a[0] = -a[0];
+ if(len_v3v3(a, mvert[ndx[1]].co) < FLT_EPSILON)
+ return 1;
+ }
+
+ return 0;
+}
+
+static void output_hull(const MVert *mvert, MFace *mface, int *totface, ListBase *tris)
+{
+ Heap *heap;
+ GHash *adj;
+ GHashIterator *iter;
+ ListBase *edges;
+ Edge *e;
+ Tri *t;
+ float score;
+
+ heap = BLI_heap_new();
+ adj = calc_edges(tris);
+
+ /* unmark all triangles */
+ for(t = tris->first; t; t = t->next)
+ t->marked = 0;
+
+ /* build heap */
+ iter = BLI_ghashIterator_new(adj);
+ while(!BLI_ghashIterator_isDone(iter)) {
+ edges = BLI_ghashIterator_getValue(iter);
+ for(e = edges->first; e; e = e->next) {
+ /* only care if the edge is used by more than
+ one triangle */
+ if(e->tri[0] && e->tri[1]) {
+ score = (e->tri[0]->area + e->tri[1]->area) *
+ dot_v3v3(e->tri[0]->no, e->tri[1]->no);
+
+ /* increase score if the triangles
+ form a symmetric quad */
+ if(is_quad_symmetric(mvert, e))
+ score *= 10;
+
+ BLI_heap_insert(heap, -score, e);
+ }
+ }
+
+ BLI_ghashIterator_step(iter);
+ }
+ BLI_ghashIterator_free(iter);
+
+ while(!BLI_heap_empty(heap)) {
+ e = BLI_heap_popmin(heap);
+
+ /* if both triangles still free, outupt as a quad */
+ if(!e->tri[0]->marked && !e->tri[1]->marked) {
+ add_quad_from_tris(mface, totface, e);
+ e->tri[0]->marked = 1;
+ e->tri[1]->marked = 1;
+ }
+ }
+
+ /* free edge list */
+ iter = BLI_ghashIterator_new(adj);
+ while(!BLI_ghashIterator_isDone(iter)) {
+ edges = BLI_ghashIterator_getValue(iter);
+ BLI_freelistN(edges);
+ MEM_freeN(edges);
+ BLI_ghashIterator_step(iter);
+ }
+ BLI_ghashIterator_free(iter);
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list