Revision: 14720
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=14720
Author: jaguarandi
Date: 2008-05-07 14:45:02 +0200 (Wed, 07 May 2008)
Log Message:
-----------
Normal projection:
+added option to remove faces where all vertices got unprojected
Nearest surface point
+15% faster closest point on point-tri function
(archived by projecting the point on tri-plane and solving the problem on 2D)
(its still using bruteforce on triangles.. I'll add the right data structure
later)
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenkernel/BKE_shrinkwrap.h
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
branches/soc-2008-jaguarandi/source/blender/makesdna/DNA_modifier_types.h
branches/soc-2008-jaguarandi/source/blender/src/buttons_editing.c
Modified:
branches/soc-2008-jaguarandi/source/blender/blenkernel/BKE_shrinkwrap.h
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/BKE_shrinkwrap.h
2008-05-07 12:23:51 UTC (rev 14719)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/BKE_shrinkwrap.h
2008-05-07 12:45:02 UTC (rev 14720)
@@ -1,5 +1,5 @@
/**
- * shrinkwrap.c
+ * BKE_shrinkwrap.h
*
* ***** BEGIN GPL LICENSE BLOCK *****
*
@@ -29,11 +29,24 @@
#ifndef BKE_SHRINKWRAP_H
#define BKE_SHRINKWRAP_H
+/* bitset stuff */
+//TODO: should move this to other generic lib files?
+typedef char* BitSet;
+#define bitset_memsize(size) (sizeof(char)*((size+7)>>3))
+
+#define bitset_new(size,name) ((BitSet)MEM_callocN(
bitset_memsize(size) , name))
+#define bitset_free(set) (MEM_freeN((void*)set))
+
+#define bitset_get(set,index) ((set)[(index)>>3] & (1 << ((index)&0x7)))
+#define bitset_set(set,index) ((set)[(index)>>3] |= (1 << ((index)&0x7)))
+
+
struct Object;
struct DerivedMesh;
struct ShrinkwrapModifierData;
+
typedef struct ShrinkwrapCalcData
{
ShrinkwrapModifierData *smd; //shrinkwrap modifier data
@@ -50,7 +63,7 @@
float keptDist; //Distance to kept from
target (units are in local space)
//float *weights; //weights of vertexs
- unsigned char *moved; //boolean indicating if vertex
has moved (TODO use bitmaps)
+ BitSet moved; //BitSet indicating if
vertex has moved
} ShrinkwrapCalcData;
Modified:
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
2008-05-07 12:23:51 UTC (rev 14719)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
2008-05-07 12:45:02 UTC (rev 14720)
@@ -22,7 +22,7 @@
*
* The Original Code is: all of this file.
*
- * Contributor(s): none yet.
+ * Contributor(s): André Pinto
*
* ***** END GPL LICENSE BLOCK *****
*/
@@ -49,7 +49,10 @@
#include "BLI_kdtree.h"
#include "RE_raytrace.h"
+#include "MEM_guardedalloc.h"
+
+/* Util macros */
#define TO_STR(a) #a
#define JOIN(a,b) a##b
@@ -82,7 +85,6 @@
#endif
-#define CONST
typedef void ( *Shrinkwrap_ForeachVertexCallback) (DerivedMesh *target, float
*co, float *normal);
@@ -189,7 +191,7 @@
//Theres some nasty thing with non-coplanar quads (that I can't
find the issue)
//so we split quads (an odd numbered face represents the second
triangle of the quad)
if(face[i-1].v4)
- RE_ray_tree_add_face(tree, 0, i*2+1);
+ RE_ray_tree_add_face(tree, 0, (RayFace*)(i*2+1));
}
RE_ray_tree_done(tree);
@@ -228,7 +230,7 @@
isec.labda = ABS(isec.labda);
VECADDFAC(isec.end, isec.start, isec.vec, isec.labda);
- return VecLenf(coord, isec.end);
+ return VecLenf((float*)coord, (float*)isec.end);
}
/*
@@ -239,7 +241,7 @@
*
* Returns FLT_MIN in parallel case
*/
-static float ray_intersect_plane(CONST float *point, CONST float *dir, CONST
float *plane_point, CONST float *plane_normal)
+static float ray_intersect_plane(const float *point, const float *dir, const
float *plane_point, const float *plane_normal)
{
float pp[3];
float a, pp_dist;
@@ -248,65 +250,174 @@
if(fabs(a) < 1e-5f) return FLT_MIN;
- VecSubf(pp, point, plane_point);
+ VECSUB(pp, point, plane_point);
pp_dist = INPR(pp, plane_normal);
return -pp_dist/a;
}
/*
- * Returns the minimum distance between the point and a triangle surface
- * Writes the nearest surface point in the given nearest
+ * This calculates the distance from point to the plane
+ * Distance is negative if point is on the back side of plane
*/
-static float nearest_point_in_tri_surface(CONST float *co, CONST float *v0,
CONST float *v1, CONST float *v2, float *nearest)
+static float point_plane_distance(const float *point, const float
*plane_point, const float *plane_normal)
{
- //TODO: make this efficient (probably this can be made with something
like 3 point_in_slice())
- if(point_in_tri_prism(co, v0, v1, v2))
- {
- float normal[3];
- float dist;
+ float pp[3];
+ VECSUB(pp, point, plane_point);
+ return INPR(pp, plane_normal);
+}
+static float choose_nearest(const float v0[2], const float v1[2], const float
point[2], float closest[2])
+{
+ float d[2][2], sdist[2];
+ VECSUB2D(d[0], v0, point);
+ VECSUB2D(d[1], v1, point);
- CalcNormFloat(v0, v1, v2, normal);
- dist = ray_intersect_plane(co, normal, v0, normal);
+ sdist[0] = d[0][0]*d[0][0] + d[0][1]*d[0][1];
+ sdist[1] = d[1][0]*d[1][0] + d[1][1]*d[1][1];
- VECADDFAC(nearest, co, normal, dist);
- return fabs(dist);
+ if(sdist[0] < sdist[1])
+ {
+ if(closest)
+ VECCOPY2D(closest, v0);
+ return sdist[0];
}
else
{
- float dist = FLT_MAX, tdist;
- float closest[3];
+ if(closest)
+ VECCOPY2D(closest, v1);
+ return sdist[1];
+ }
+}
+/*
+ * calculates the closest point between point-tri (2D)
+ * returns that tri must be right-handed
+ * Returns square distance
+ */
+static float closest_point_in_tri2D(const float point[2], const float
tri[3][2], float closest[2])
+{
+ float edge_di[2];
+ float v_point[2];
+ float proj[2]; //point projected over
edge-dir, edge-normal (witouth normalized edge)
+ const float *v0 = tri[2], *v1;
+ float edge_slen, d; //edge squared length
+ int i;
+ const float *nearest_vertex = NULL;
- PclosestVL3Dfl(closest, co, v0, v1);
- tdist = VecLenf(co, closest);
- if(tdist < dist)
- {
- dist = tdist;
- VECCOPY(nearest, closest);
- }
- PclosestVL3Dfl(closest, co, v1, v2);
- tdist = VecLenf(co, closest);
- if(tdist < dist)
+ //for each edge
+ for(i=0, v0=tri[2], v1=tri[0]; i < 3; v0=tri[i++], v1=tri[i])
+ {
+ VECSUB2D(edge_di, v1, v0);
+ VECSUB2D(v_point, point, v0);
+
+ proj[1] = v_point[0]*edge_di[1] - v_point[1]*edge_di[0];
//dot product with edge normal
+
+ //point inside this edge
+ if(proj[1] < 0)
+ continue;
+
+ proj[0] = v_point[0]*edge_di[0] + v_point[1]*edge_di[1];
+
+ //closest to this edge is v0
+ if(proj[0] < 0)
{
- dist = tdist;
- VECCOPY(nearest, closest);
+ if(nearest_vertex == NULL || nearest_vertex == v0)
+ nearest_vertex = v0;
+ else
+ {
+ //choose nearest
+ return choose_nearest(nearest_vertex, v0,
point, closest);
+ }
+ i++; //We can skip next edge
+ continue;
}
- PclosestVL3Dfl(closest, co, v2, v0);
- tdist = VecLenf(co, closest);
- if(tdist < dist)
+ edge_slen = edge_di[0]*edge_di[0] + edge_di[1]*edge_di[1];
//squared edge len
+ //closest to this edge is v1
+ if(proj[0] > edge_slen)
{
- dist = tdist;
- VECCOPY(nearest, closest);
+ if(nearest_vertex == NULL || nearest_vertex == v1)
+ nearest_vertex = v1;
+ else
+ {
+ return choose_nearest(nearest_vertex, v1,
point, closest);
+ }
+ continue;
}
- return dist;
+ //nearest is on this edge
+ d= proj[1] / edge_slen;
+ closest[0] = point[0] - edge_di[1] * d;
+ closest[1] = point[1] + edge_di[0] * d;
+
+ return proj[1]*proj[1]/edge_slen;
}
+
+ if(nearest_vertex)
+ {
+ VECSUB2D(v_point, nearest_vertex, point);
+ VECCOPY2D(closest, nearest_vertex);
+ return v_point[0]*v_point[0] + v_point[1]*v_point[1];
+ }
+ else
+ {
+ VECCOPY(closest, point); //point is already inside
+ return 0.0f;
+ }
}
+/*
+ * Returns the square of the minimum distance between the point and a triangle
surface
+ * If nearest is not NULL the nearest surface point is written on it
+ */
+static float nearest_point_in_tri_surface(const float *point, const float *v0,
const float *v1, const float *v2, float *nearest)
+{
+ //Lets solve the 2D problem (closest point-tri)
+ float normal_dist, plane_sdist, plane_offset;
+ float du[3], dv[3], dw[3]; //orthogonal axis (du=(v0->v1),
dw=plane normal)
+ float p_2d[2], tri_2d[3][2], nearest_2d[2];
+ CalcNormFloat((float*)v0, (float*)v1, (float*)v2, dw);
+
+ //point-plane distance and calculate axis
+ normal_dist = point_plane_distance(point, v0, dw);
+
+ VECSUB(du, v1, v0);
+ Normalize(du);
+ Crossf(dv, dw, du);
+ plane_offset = INPR(v0, dw);
+
+ //project stuff to 2d
+ tri_2d[0][0] = INPR(du, v0);
+ tri_2d[0][1] = INPR(dv, v0);
+
+ tri_2d[1][0] = INPR(du, v1);
+ tri_2d[1][1] = INPR(dv, v1);
+
+ tri_2d[2][0] = INPR(du, v2);
+ tri_2d[2][1] = INPR(dv, v2);
+
+ p_2d[0] = INPR(du, point);
+ p_2d[1] = INPR(dv, point);
+
+ //we always have a right-handed tri
+ //this should always happen because of the way normal is calculated
+ plane_sdist = closest_point_in_tri2D(p_2d, tri_2d, nearest_2d);
+
+ //project back to 3d
+ if(nearest)
+ {
+ nearest[0] = du[0]*nearest_2d[0] + dv[0] * nearest_2d[1] +
dw[0] * plane_offset;
+ nearest[1] = du[1]*nearest_2d[0] + dv[1] * nearest_2d[1] +
dw[1] * plane_offset;
+ nearest[2] = du[2]*nearest_2d[0] + dv[2] * nearest_2d[1] +
dw[2] * plane_offset;
+ }
+
+ return sasqrt(plane_sdist + normal_dist*normal_dist);
+}
+
+
+
/*
* Shrink to nearest surface point on target mesh
*/
@@ -321,7 +432,7 @@
MVert *vert = target->getVertDataArray(target, CD_MVERT);
MFace *face = target->getFaceDataArray(target, CD_MFACE);
- VECCOPY(orig_co, co);
+ VECCOPY(orig_co, co);
for (i = 0; i < numFaces; i++)
{
@@ -476,6 +587,112 @@
}
}
+
+/*
+ * This function removes Unused faces, vertexs and edges from calc->target
+ *
+ * This function may modify calc->final. As so no data retrieved from
+ * it before the call to this function can be considered valid
+ * In case it creates a new DerivedMesh, the old calc->final is freed
+ */
+//TODO memory checks on allocs
+static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
+{
+ int i, t;
+
+ DerivedMesh *old = calc->final, *new = NULL;
+ MFace *new_face = NULL;
+ MVert *new_vert = NULL;
+
+ int numVerts= old->getNumVerts(old);
+ MVert *vert = old->getVertDataArray(old, CD_MVERT);
+
+ int numFaces= old->getNumFaces(old);
+ MFace *face = old->getFaceDataArray(old, CD_MFACE);
+
+ BitSet moved_verts = calc->moved;
+
+ //Arrays to translate to new vertexs indexs
+ int *vert_index = (int*)MEM_callocN(sizeof(int)*(numVerts), "shrinkwrap
used verts");
+ BitSet used_faces = bitset_new(numFaces, "shrinkwrap used faces");
+ int numUsedFaces = 0;
+
+ //calc real number of faces, and vertices
+ //Count used faces
+ for(i=0; i<numFaces; i++)
+ {
+ char res = bitset_get(moved_verts, face[i].v1)
+ | bitset_get(moved_verts, face[i].v2)
+ | bitset_get(moved_verts, face[i].v3)
+ | (face[i].v4 ? bitset_get(moved_verts,
face[i].v4) : 0);
+
+ if(res)
+ {
+ bitset_set(used_faces, i); //Mark face to maintain
+ numUsedFaces++;
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
