473,320 Members | 1,828 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Re: using realloc for a dynamically growing array

On Fri, 27 Jun 2008 09:28:56 -0700 (PDT), pereges
<Br*****@gmail.comwrote:
>On Jun 27, 3:55 pm, "Bartc" <b...@freeuk.comwrote:
>So, you have one parent array, and just the one child array?
>In this case I don't think there's any question that a one-time scan of the
10-million element parent (taking milliseconds) will be faster than
potentially calling realloc millions of times.

Well actually the array is to be split into two child arrays. The
child arrays will also be split. Sort of like binary tree .The array
has to be split at the median value such that the left array
contains all elements <= median and right array contains elements >
median. For eg.

1 2 3 3 4 5 6

median is 3

the left array is

1 2 3 3

right array is

4 5 6

Because the parent array of size n is split at the median , it is
bound to happen that both child arrays size is >= n/2. So we can
malloc child arrays of size n/2 and from there on keep calling realloc
till all the elements are placed properly. The other much faster
option is double the allocated size each time the array reaches its
limit and more data is to be added. Ofcourse, the backdrop of this
method is that a lot of space will be wasted. I am not sure if you can
use realloc() to reduce the array to the actual size at the end. Most
sources that I've read say that its not possible in all
implementations.
There are some obvious questions that should be asked, e.g., is
the contents of your array already sorted as your example
implies. If they are then all you need to do is find the element
at index k = n/2 and then increase k until you find an element
that differs from A[n/2]. Then k is the number of left children
and n-k is the number of right children. (Fencepost correction
needed.)

Now if the data is scrambled and you know the median:
(1) Allocate an array of size n.
(2) Go through the original array sequentially.
(3) Fill in the new array bottom up with 'small' elements
and top down with 'big' elements. Keep a count of the
number of 'small' elements. Call it k. Then the first
k elements of the new array are small, and the last n-k
elements are big.
(4) If stability is important, reverse the 'big' elements
segment.

Done.
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
Jun 27 '08 #1
1 4829
I'm trying to build a kdtree for a 3d object. An object contains
vertices(3d vectors) and triangles (triangular mesh structure). The
idea behind using a kdtree is to split the bounding box(a minimum
volume box which encompasses the entire object) at the root node (i.e.
the one which contains the object itself) recursively into smaller
boxes until some stopping condition is satisfied ( I'm using a
combination of depth and maximum permissible triangles inside a box).
The box at the root node will be split along the x axis, the two
resulting children along y axis and the grandchildren along z axis.
This is repeated in a cyclical fashion. I'm splitting the box at the
point which resembles the median point of all vertices inside a given
box. The triangles are split by comparing the three vertex coordinates
against the split point and they can be put in either left child ,
right child or both children(in case when the triangle intersects
splitting plane). I can also use some other criterion like mid point
but median is supposed to give a better split. I want to use this kd
tree for accelerating my ray tracing procedure. With a kdtree, all you
have to do is check against intersection between a ray and the
boxes(which is extremely fast) until you reach a leaf node (which
contains a minimum number of triangles). Now all you need to do is
test for intersection against a minimal number of triangles which is a
lot faster than checking for intersection of every ray with every
triangle in the mesh. Ultimately, almost every triangle can be traced
to a leaf node (which will not be further split btw).

Here's the data structure that I have written for kd tree node
typedef struct kdnode_s
{
/* bounding box */
bbox box;

/* 0 - split along x axis , 1 - split along y axis, 2 - split along
z axis */
int splitplane;
union
{
/* Used only for non-leaf nodes i.e. split plane != -1 */
struct
{
struct kdnode_s *child[2]; /* pointers to two children */
double split; /* splitting coordinate */

}nonleaf;

/* Used for leaf nodes i.e. split plane = -1 */
struct
{
int ntriangles; /* number of triangles in node */
triangle **triptrlist; /* pointer to an array of pointers to
triangles */

}leaf;

}u;

}kdnode;

Note that I do not store the vertex list in every kd tree node, I
don't think its necessary because
ultimately we are only using the vertex list for finding split point,
its the triangles that we are interested in.

Now the function(smaller version) which partitions the kd tree looks
as follows:

/
************************************************** ************************************************** ***************************/
/* The arguments to this subidivide_kdtree
function:
*/
/* kd - pointer to kd tree node. Initially pointer of root node is
passed. */
/* m - pointer to the
mesh
*/
/* depth - depth of subidivision (0 when calling for first
time)
*/
/* maxdepth - maximum depth permissible (passed as argument when
calling for first time) */
/* maxtriangles - maximum number of triangles permissible
*/
/* pvertptrlist - parent vertex list */
/* ptriptrlist - parent triangle ptr
list
*/
/* pnvert - number of vertices in parent
node
*/
/* pntri - number of triangles in parent
node
*/
/
************************************************** ************************************************** ********************/

int subdivide_kdtree(kdnode *kd, mesh *m, int depth, int maxdepth, int
maxtriangles,
vector **pvertptrlist, triangle *ptriptrlist, int
pnvert, int pntri)
{
/* cntri - number of triangles in child, cnvert - number of
triangles in child */
int i, j, k, cntri, cnvert;
triangle **ctriptrlist; /* pointer to child triangle pointer array
*/
vector **cvertptrlist; /* pointer to child vertices pointer array */
int flag = 0; /* error flag */

kd->splitplane = -1; /* initialize current node as the leaf node */
kd->u.leaf.ntriangles = pntri;
kd->u.leaf.triptrlist = ptriptrlist;

/* If this condition is true, then its a non leaf node which will be
divided */
if(pntri maxtriangles && (depth < maxdepth))
{
kd->splitplane = depth % 3;

/* sort the array of pointers */
quicksort(pvertptrlist, 0, pnvert - 1, kd->splitplane);

/* find the split point for parent node */
kd->u.nonleaf.split = find_split_point(pvertptrlist, pnvert - 1,
kd->splitplane);

/* process both children nodes */
for(i = 0; i < 2; i++)
{
/* Allocate memory and perform other initializations for both
children */
/* Now partition the parent vertex and triangle list */

cnvert = 0;
for(j = 0; j < pnvert; j++)
{
/* Count number of vertices inside current child box being
processed */

if(vertex_inside_box(pvertptrlist[j]->coord[kd->splitplane],
kd->u.nonleaf.split, i))
cnvert += 1;
}

/* Allocate memory for child vertex pointer list */

cvertptrlist = malloc(sizeof(vector *) * cnvert);

/* Put the parent vertices into child node */

cnvert = 0;
for(j = 0; j < pnvert; j++)
{
if(vertex_inside_box(pvertlist[j]->coord[kd->splitplane], kd-
>u.nonleaf.split, i))
cvertlist[cnvert++] = pvertlist[j];
}

/* Do similar steps for partitioning the triangle */

flag = subdivide_kdtree(kd->u.nonleaf.child[i], m, depth + 1,
maxdepth,
maxtriangles, cvertptrlist,ctriptrlist,
cnvert, cntri);
}
}
return (flag);
}
Jun 27 '08 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Andreas Bauer | last post by:
I've got an array in the vein of MyType* array; arry = new MyType; This of course works fine, but I have the need to dynamically grow the boundaries of that array at runtime. I can't seem to...
7
by: Fabian Wauthier | last post by:
Hi list, I am trying to dynamically grow a 2 dimensional array (Atom ***Screen) of pointers to a struct Atom (i.e. the head of a linked list). I am not sure if this is the right way to do it: ...
4
by: John | last post by:
I'm trying (struggling) to use realloc to grow a list of strings. The number of strings is not known (this is a subset of an assignment to write a recursive ls program... my BS was in EE, so I'm...
5
by: D² | last post by:
Hello, I was trying to enlarge the size of an array wqith this code: float data ; data = realloc (data, n*sizeof(float)); but I encountered an error during compile fase, is this sintax...
18
by: ifmusic | last post by:
I used to think that i knew to program in C but this problem is making me thing otherwise. i'm trying to do something trivial, i suppose. i have this struct: typedef struct{ int socket; char...
7
by: Mischa | last post by:
Hello, I am trying to use realloc multiple times to extend an array of doubles but unfortunatly it keeps failing. I think I am mixing up the size to which the old memory block needs to be...
7
by: Jonathan Shan | last post by:
Hello all, I am trying to run a program which has dynamic array of type struct. The program works until the line which uses realloc function to allocate more memory. I have tried to reproduce...
31
by: banansol | last post by:
Hi, I just want to get this right. A call to realloc() will return NULL on error and the original memory is left untouched, both when requesting a larger or a smaller size that the original,...
0
by: pereges | last post by:
On Jun 27, 11:42 pm, j...@smof.fiawol.org (J. Cochran) wrote: ok i will post some code and explanation.
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.