Hello, a week or so ago, there was a request on comp.graphics.apps.gimp about the availability of the PS extrude-filter, used for example in this tutorial: http://www.voidix.com/cystal.html I spent a couple of hours working on a GIMP equivalent and I am attaching a horrible sample picture created with the plug-in as it stands so far (it currently uses random values for the colours of the pyramids and knows nothing about anti-aliasing). I'm for now using a quick and terrible hack to fill the triangles (see attached source if you are curious) and want to ask: Which method do you recommend to fill lots of triangles from within a plug-in? Is there a (fast?) Gimp function for this that I can use, maybe capable of anti-aliasing? I think there is no obvious way to use tile iterators for this effect (little spatial locality), I am currently (g|s)etting the whole image at once - would you recommend that I get and set a region for each triangle I draw or some better compromise? I have not tried it yet - could it be too slow if there are very many triangles, or slower than the swapping that could happen when processing the whole image at once? I'm asking this because I could only benchmark on my own system, which hardly is representative. Best regards, Markus. External links: Current version of the plug-in: http://stud4.tuwien.ac.at/~e0225855/extrude.c Horrible picture mentioned: http://stud4.tuwien.ac.at/~e0225855/extrude.png
Attachment:
extrude.png
Description: PNG image
/* The GIMP -- an image manipulation program
* Copyright (C) 1995 Spencer Kimball and Peter Mattis
*
* 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
/* Plug-in (eventually) implementing Photoshop's "Extrude" effect
Written by Markus Triska <triska@xxxxxx>
August 2nd, 2004 - far from finished, just started working on it */
#include <stdio.h>
#include <stdlib.h>
#include <libgimp/gimp.h>
static void query (void);
static void run (const char *name,
gint nparams,
const GimpParam *param,
gint *nreturn_vals,
GimpParam **return_vals);
static void extrude_render (GimpDrawable *drawable);
struct MemImage {
long bpp;
guchar *data;
gint width, height, halfwidth, halfheight;
} theimage;
typedef struct pyramid_tag {
GimpVector3 triangles[4][3]; /* four triangles */
GimpRGB colours[4];
int order[4];
} Pyramid;
GimpPlugInInfo PLUG_IN_INFO =
{
NULL, /* init_proc */
NULL, /* quit_proc */
query, /* query_proc */
run, /* run_proc */
};
void
lines_intersection(GimpVector2 p1, GimpVector2 p2,
GimpVector2 p3, GimpVector2 p4,
GimpVector2 *intersectionpoint)
{
float a1,b1,c1, /* constants of linear equations */
a2,b2,c2,
det_inv, /* the inverse of the determinant of the coefficient */
m1,m2; /* the slopes of each line */
/* compute slopes, note the kludge for infinity, however, this will
be close enough */
if ((p2.x-p1.x)!=0)
m1 = (p2.y-p1.y)/(p2.x-p1.x);
else
m1 = (float)1e+10; /* close enough to infinity */
if ((p4.x-p3.x)!=0)
m2 = (p4.y-p3.y)/(p4.x-p3.x);
else
m2 = (float)1e+10; /* close enough to infinity */
/* compute constants */
a1 = m1;
a2 = m2;
b1 = -1;
b2 = -1;
c1 = (p1.y-m1*p1.x);
c2 = (p3.y-m2*p3.x);
/* compute the inverse of the determinant */
det_inv = 1/(a1*b2 - a2*b1);
/* use Cramer's rule to compute x and y */
intersectionpoint->x=((b1*c2 - b2*c1)*det_inv);
intersectionpoint->y=((a2*c1 - a1*c2)*det_inv);
}
static void
fill_triangle(struct MemImage memimg, GimpVector2 *points, GimpRGB rgb)
{
GimpVector2 tempvector,intersec1,intersec2;
gint curr_y, sortruns = 0;
if ((points[0].y == points[1].y) && (points[1].y == points[2].y)) return;
/*
We enforce the following order on the points:
(a) non-decreasing y coordinates
(b) for y1 == y2, the point with lower x comes first
This leaves 4 types of triangles to handle:
0 1 0 0 0
---- / \ /| |\
| / / \ 1 / | | \ 1
|/ |-----\ \ | | /
2 1 2 \|2 2|/
*/
GimpVector2 sortedpoints[3];
sortedpoints[0] = points[0]; sortedpoints[1] = points[1];
sortedpoints[2] = points[2];
for (sortruns = 0; sortruns < 3; sortruns++) {
int offset = sortruns % 2;
if (sortedpoints[offset].y > sortedpoints[offset+1].y) {
tempvector = sortedpoints[offset];
sortedpoints[offset] = sortedpoints[offset+1];
sortedpoints[offset+1] = tempvector;
}
}
for (sortruns = 0; sortruns < 2; sortruns++) {
if (sortedpoints[sortruns].y == sortedpoints[sortruns+1].y) {
if (sortedpoints[sortruns].x == sortedpoints[sortruns+1].x) return;
if (sortedpoints[sortruns].x > sortedpoints[sortruns+1].x) {
tempvector = sortedpoints[sortruns];
sortedpoints[sortruns] = sortedpoints[sortruns+1];
sortedpoints[sortruns+1] = tempvector;
}
}
}
/* start from (one) topmost point of the triangle */
for (curr_y = (gint) sortedpoints[0].y; curr_y <= sortedpoints[2].y; curr_y++)
{
gint startx, endx, i;
if (curr_y > sortedpoints[1].y) {
lines_intersection (sortedpoints[1], sortedpoints[2], gimp_vector2_new(0, curr_y), gimp_vector2_new(memimg.width, curr_y), &intersec1);
if (sortedpoints[1].y == sortedpoints[2].y)
intersec1.x = sortedpoints[1].x;
} else {
lines_intersection (sortedpoints[0], sortedpoints[1], gimp_vector2_new(0, curr_y), gimp_vector2_new(memimg.width, curr_y), &intersec1);
if (sortedpoints[0].y == sortedpoints[1].y)
intersec1.x = sortedpoints[0].x;
}
lines_intersection (sortedpoints[0], sortedpoints[2], gimp_vector2_new(0, curr_y), gimp_vector2_new(memimg.width, curr_y), &intersec2);
startx = (intersec1.x < intersec2.x) ? intersec1.x : intersec2.x;
endx = (intersec2.x > intersec1.x) ? intersec2.x : intersec1.x;
/* printf("I am at y %d, and will fill x from %d to %d\n", curr_y, startx, endx); */
for (i = startx; i <= endx; i++)
{
long offset = (memimg.width * curr_y + i)*memimg.bpp;
memimg.data[offset] = rgb.r;
memimg.data[offset+1] = rgb.g;
memimg.data[offset+2] = rgb.b;
}
}
}
GimpVector2 point_to2d(GimpVector3 point3d)
{
GimpVector2 ret;
gint zstrich = 150;
ret.x = zstrich/(zstrich + point3d.z)*point3d.x + theimage.halfwidth;
ret.y = zstrich/(zstrich + point3d.z)*point3d.y + theimage.halfheight;
/*
ret.x = point3d.x + theimage.halfwidth;
ret.y = point3d.y + theimage.halfheight;
*/
return ret;
}
void drawtriangles(struct MemImage memimg, GimpVector3 triangles[4][3], int order[4], GimpRGB cols[4])
{
int i;
GimpVector2 temp;
temp = point_to2d(triangles[0][0]);
/*
first element will always be the tip of the pyramid
TODO: implement Photoshop "DON'T hide partially visible elements"
*/
if (temp.x > memimg.width || temp.x < 0 ||
temp.y > memimg.height || temp.y < 0) return;
for (i = 0; i <= 3; i++) {
GimpVector2 points2D[3];
points2D[0] = point_to2d(triangles[order[i]][0]);
points2D[1] = point_to2d(triangles[order[i]][1]);
points2D[2] = point_to2d(triangles[order[i]][2]);
fill_triangle(memimg, points2D, cols[order[i]]);
}
}
MAIN ()
static void
query ()
{
static GimpParamDef args[] =
{
{ GIMP_PDB_INT32, "run_mode", "Interactive, non-interactive" },
{ GIMP_PDB_IMAGE, "image", "Input image" },
{ GIMP_PDB_DRAWABLE, "drawable", "Input drawable" }
};
gimp_install_procedure ("plug_in_extrude",
"Extrude image",
"Create 3D pyramids or blocks.",
"Markus Triska <triska@xxxxxx>",
"Markus Triska",
"2004",
"<Image>/Extrude",
"RGB*",
GIMP_PLUGIN,
G_N_ELEMENTS(args), 0,
args, NULL);
}
static void
run (const char *name,
gint nparams,
const GimpParam *param,
gint *nreturn_vals,
GimpParam **return_vals)
{
static GimpParam values[1];
GimpDrawable *drawable;
GimpRunMode run_mode;
GimpPDBStatusType status = GIMP_PDB_SUCCESS;
gint32 image_ID;
run_mode = param[0].data.d_int32;
/* Get the specified drawable */
drawable = gimp_drawable_get (param[2].data.d_drawable);
image_ID = param[1].data.d_image;
/* Make sure that the drawable is RGB color */
if (gimp_drawable_is_rgb (drawable->drawable_id))
{
/* gimp_progress_init ("Creating Stripes...");
gimp_tile_cache_ntiles (2 * (drawable->width / gimp_tile_width () + 1)); */
extrude_render (drawable);
if (run_mode != GIMP_RUN_NONINTERACTIVE)
gimp_displays_flush ();
}
else
{
status = GIMP_PDB_EXECUTION_ERROR;
}
*nreturn_vals = 1;
*return_vals = values;
values[0].type = GIMP_PDB_STATUS;
values[0].data.d_status = status;
gimp_drawable_detach (drawable);
}
static int pyramid_comparison(const void *p1, const void *p2)
{
/*
we want to draw pyramids far away from the center first (painter's method)
use the tip of the pyramid as reference point
*/
gint dist1, dist2;
Pyramid *pyr1 = (Pyramid *) p1;
Pyramid *pyr2 = (Pyramid *) p2;
gint p1x = pyr1->triangles[0][0].x, p1y = pyr1->triangles[0][0].y;
gint p2x = pyr2->triangles[0][0].x, p2y = pyr2->triangles[0][0].y;
dist1 = p1x*p1x + p1y*p1y;
dist2 = p2x*p2x + p2y*p2y;
if (dist1 == dist2) return 0;
if (dist1 > dist2) return -1;
return 1;
}
static void
extrude_render (GimpDrawable *drawable)
{
GimpPixelRgn src_rgn, dest_rgn;
guchar *src, *dest;
gint progress, max_progress;
gint has_alpha, red, green, blue;
gint x1, y1, x2, y2, imgmemsize, imgwidth, imgheight;
gint i, pyramid_index = 0, num_pyramids;
gint size = 20, halfsize = size/2;
GimpVector2 testpoints[3];
Pyramid *allpyramids;
GimpRGB testcolour;
long bpp;
gint curr_x, curr_y;
/* Get selection area */
gimp_drawable_mask_bounds (drawable->drawable_id, &x1, &y1, &x2, &y2);
imgwidth = x2 - x1;
imgheight = y2 - y1;
has_alpha = gimp_drawable_has_alpha (drawable->drawable_id);
red = 0; green = 1; blue = 2;
bpp = drawable->bpp;
theimage.bpp = drawable->bpp;
theimage.width = imgwidth;
theimage.halfwidth = imgwidth/2;
theimage.height = imgheight;
theimage.halfheight = imgheight/2;
/* Initialize progress */
progress = 0;
max_progress = imgwidth * imgheight;
/* substitute pixel vales */
gimp_pixel_rgn_init (&src_rgn, drawable,
x1, y1, imgwidth, imgheight, FALSE, FALSE);
gimp_pixel_rgn_init (&dest_rgn, drawable,
x1, y1, imgwidth, imgheight, TRUE, TRUE);
imgmemsize = bpp * imgwidth * imgheight * sizeof(guchar);
src = (guchar *) g_malloc(imgmemsize);
dest = (guchar *) g_malloc(imgmemsize);
theimage.data = dest;
allpyramids = (Pyramid *) g_malloc((imgwidth/size + 1)*(imgheight/size + 1)*sizeof(Pyramid));
gimp_pixel_rgn_get_rect(&src_rgn, src, x1, y1, imgwidth, imgheight);
for (curr_y = 0; curr_y+size < imgheight; curr_y += size) {
for (curr_x = 0; curr_x+size < imgwidth; curr_x += size)
{
/*
build a single pyramid, store with "virtual coordinates", where
center of image = (0,0,0)
*/
Pyramid pyr;
GimpVector3 topleft, topright, botleft, botright, tip;
topleft = gimp_vector3_new(curr_x-theimage.halfwidth, curr_y-theimage.halfheight, 0);
topright = gimp_vector3_new(curr_x + size - theimage.halfwidth, curr_y - theimage.halfheight, 0);
botleft = gimp_vector3_new(curr_x - theimage.halfwidth, curr_y + size - theimage.halfheight, 0);
botright = gimp_vector3_new(curr_x + size - theimage.halfwidth, curr_y + size - theimage.halfheight, 0);
tip = gimp_vector3_new(topleft.x + halfsize, topleft.y + halfsize , -80);
for (i = 0; i <= 3; i++) pyr.triangles[i][0] = tip;
/* top */
pyr.triangles[0][1] = topleft; pyr.triangles[0][2] = topright;
/* right */
pyr.triangles[1][1] = topright; pyr.triangles[1][2] = botright;
/* bottom */
pyr.triangles[2][1] = botright; pyr.triangles[2][2] = botleft;
/* left */
pyr.triangles[3][1] = topleft; pyr.triangles[3][2] = botleft;
if (curr_y < theimage.halfheight) {
if (curr_x < theimage.halfwidth) {
pyr.order[0] = 3; pyr.order[1] = 0; pyr.order[2] = 1; pyr.order[3] = 2;
} else {
pyr.order[0] = 1; pyr.order[1] = 0; pyr.order[2] = 3; pyr.order[3] = 2;
}
} else {
if (curr_x < theimage.halfwidth) {
pyr.order[0] = 3; pyr.order[1] = 2; pyr.order[2] = 1; pyr.order[3] = 0;
} else {
pyr.order[0] = 1; pyr.order[1] = 2; pyr.order[2] = 3; pyr.order[3] = 0;
}
}
for (i = 0; i <= 3; i++) {
pyr.colours[i].r = rand() % 255;
pyr.colours[i].g = rand() % 255;
pyr.colours[i].b = rand() % 255;
}
allpyramids[pyramid_index] = pyr;
pyramid_index++;
}
}
num_pyramids = pyramid_index;
qsort(allpyramids, num_pyramids, sizeof(Pyramid), pyramid_comparison);
for (i = 0; i < num_pyramids; i++) {
Pyramid pyr = allpyramids[i];
drawtriangles(theimage, pyr.triangles, pyr.order, pyr.colours);
}
for (i = 0; i < 50; i++)
{
/* dest[imgwidth*i*bpp] = 254; dest[(imgwidth*i + 3)*bpp] = 254; dest[(imgwidth*i + 6)*bpp] = 254; */
}
testpoints[0] = gimp_vector2_new(50, 50);
testpoints[1] = gimp_vector2_new(0, 100);
testpoints[2] = gimp_vector2_new(100, 100);
testcolour.r = 254;
testcolour.g = 254;
testcolour.b = 254;
/* fill_triangle(memimg, testpoints, testcolour); */
/*
testpoints[0] = gimp_vector2_new(0, 80);
testcolour.b = 170;
fill_triangle(memimg, testpoints, testcolour);
testpoints[0] = gimp_vector2_new(100,100);
testpoints[1] = gimp_vector2_new(180,100);
testpoints[2] = gimp_vector2_new(180,150);
fill_triangle(memimg, testpoints, testcolour);
*/
gimp_pixel_rgn_set_rect(&dest_rgn, dest, x1, y1, imgwidth, imgheight);
g_free(src);
g_free(dest);
g_free(allpyramids);
/* Update progress
progress += src_rgn.w * src_rgn.h;
gimp_progress_update ((double) progress / (double) max_progress); */
/* update the region */
gimp_drawable_flush (drawable);
gimp_drawable_merge_shadow (drawable->drawable_id, TRUE);
gimp_drawable_update (drawable->drawable_id, x1, y1, (x2 - x1), (y2 - y1));
}
