/*************************************************************************/
/*                                                                       */
/*  Copyright (c) 1994 Stanford University                               */
/*                                                                       */
/*  All rights reserved.                                                 */
/*                                                                       */
/*  Permission is given to use, copy, and modify this software for any   */
/*  non-commercial purpose as long as this copyright notice is not       */
/*  removed.  All other uses, including redistribution in whole or in    */
/*  part, are forbidden without prior written permission.                */
/*                                                                       */
/*  This software is provided with absolutely no warranty and no         */
/*  support.                                                             */
/*                                                                       */
/*************************************************************************/

/************************************************************************
 *
 *	Class methods for small simple objects.
 *
 *
 *************************************************************************/
  
#include <stdio.h>
  
EXTERN_ENV;
  
include(radiosity.h)

struct {
    char pad1[PAGE_SIZE];	 	/* padding to avoid false-sharing 
        and allow page-placement */	
    int          n_local_free_elemvertex    ;
    ElemVertex  *local_free_elemvertex      ;
    int    n_local_free_edge    ;
    Edge  *local_free_edge      ;
    int lock_alloc_counter  ;
    char pad2[PAGE_SIZE];	 	/* padding to avoid false-sharing 
        and allow page-placement */	
} sobj_struct[MAX_PROCESSORS];

  
/***************************************************************************
****************************************************************************
*
*    Methods for Vertex object
*
****************************************************************************
****************************************************************************/

/***************************************************************************
 *
 *    vector_length()
 *
 *    Comute length of a vector represented by Vertex
 *    length = | v | 
 *
 ****************************************************************************/
  
  float vector_length( v )
  
  Vertex *v ;
{
    double t0, t1, t2 ;
    
    t0 = v->x * v->x ;
    t1 = v->y * v->y ;
    t2 = v->z * v->z ;
    
    return( sqrt( t0 + t1 + t2 ) ) ;
}


/***************************************************************************
*
*    distance()
  *
  *    Comute distance of two points.
  *    dist = | P1 - P2 | 
  *
  ****************************************************************************/
  
  float distance( p1, p2 )
  
  Vertex *p1, *p2 ;
{
    Vertex v12 ;
    
    v12.x = p2->x - p1->x ;
    v12.y = p2->y - p1->y ;
    v12.z = p2->z - p1->z ;
    
    return( vector_length( &v12 ) ) ;
}

/***************************************************************************
*
*    normalize_vector()
  *
  *    Normalize vector represented by Vertex
  *    v1 <- normalized( v2 )
  *
  ****************************************************************************/
  
  float normalize_vector( v1, v2 )
  
  Vertex *v1, *v2 ;
{
    float t0 ;
    float length ;
    
    length = vector_length( v2 ) ;
    t0 = (float)1.0 / length ;
    
    v1->x = v2->x * t0 ;
    v1->y = v2->y * t0 ;
    v1->z = v2->z * t0 ;
    
    return( length ) ;
}


/**************************************************************************
*
*    inner_product()
  *
  *          (v1.v2) <- inner_product( v1, v2 )
  *
  ***************************************************************************/
  
  float inner_product( v1, v2 )
  
  Vertex *v1, *v2 ;
{
    float ip ;
    
    ip  = v1->x * v2->x ;
    ip += v1->y * v2->y ;
    ip += v1->z * v2->z ;
    
    return( ip ) ;
}


/**************************************************************************
*
*    cross_product()
  *
  *          Vc = V1 X V2
  *
  ***************************************************************************/
  
  void cross_product( vc, v1, v2 )
  
  Vertex *vc, *v1, *v2 ;
{
    vc->x = v1->y * v2->z  -  v1->z * v2->y ;
    vc->y = v1->z * v2->x  -  v1->x * v2->z ;
    vc->z = v1->x * v2->y  -  v1->y * v2->x ;
}


/**************************************************************************
*
*    plane_normal()
  *
  *          Vc = (P2-P1) X (P3-P1) /  |(P2-P1) X (P3-P1)|
  *
  ***************************************************************************/
  
  float plane_normal( vc, p1, p2, p3 )
  
  Vertex *vc, *p1, *p2, *p3 ;
{
    Vertex v1, v2 ;
    
    /* Compute vectors */
    v1.x = p2->x - p1->x ;
    v1.y = p2->y - p1->y ;
    v1.z = p2->z - p1->z ;
    
    v2.x = p3->x - p1->x ;
    v2.y = p3->y - p1->y ;
    v2.z = p3->z - p1->z ;
    
    /* Compute cross product and normalize */
    cross_product( vc, &v1, &v2 ) ;
    return( normalize_vector( vc, vc ) ) ;
}


/**************************************************************************
*
*    center_point()
  *
  *          P = (P1 + P2 + P3) / 3
  *
  ***************************************************************************/
  
  void center_point( p1, p2, p3, pc )
  
  Vertex *p1, *p2, *p3 ;		/* 3 vertices of a triangle */
  Vertex *pc ;			/* Center point (RETURNED) */
{
    /* Compute mid point of the element */
    
    pc->x = (p1->x + p2->x + p3->x) * (float)(1.0/3.0) ;
    pc->y = (p1->y + p2->y + p3->y) * (float)(1.0/3.0) ;
    pc->z = (p1->z + p2->z + p3->z) * (float)(1.0/3.0) ;
}


/**************************************************************************
*
*    four_center_points()
  *
  *          P = (P1 + P2 + P3) / 3
  *
  ***************************************************************************/
  
  void four_center_points( p1, p2, p3, pc, pc1, pc2, pc3 )
  
  Vertex *p1, *p2, *p3 ;		/* 3 vertices of a triangle */
  Vertex *pc ;			/* Center point (RETURNED) */
  Vertex *pc1, *pc2, *pc3 ;		/* Center points (RETURNED) */
{
    /* Compute mid point of the element */
    pc->x  = (p1->x + p2->x + p3->x) * (float)(1.0/3.0) ;
    pc->y  = (p1->y + p2->y + p3->y) * (float)(1.0/3.0) ;
    pc->z  = (p1->z + p2->z + p3->z) * (float)(1.0/3.0) ;
    
    pc1->x = (p1->x * 4 + p2->x + p3->x) * (float)(1.0/6.0) ;
    pc1->y = (p1->y * 4 + p2->y + p3->y) * (float)(1.0/6.0) ;
    pc1->z = (p1->z * 4 + p2->z + p3->z) * (float)(1.0/6.0) ;
    
    pc2->x = (p1->x + p2->x * 4 + p3->x) * (float)(1.0/6.0) ;
    pc2->y = (p1->y + p2->y * 4 + p3->y) * (float)(1.0/6.0) ;
    pc2->z = (p1->z + p2->z * 4 + p3->z) * (float)(1.0/6.0) ;
    
    pc3->x = (p1->x + p2->x + p3->x * 4) * (float)(1.0/6.0) ;
    pc3->y = (p1->y + p2->y + p3->y * 4) * (float)(1.0/6.0) ;
    pc3->z = (p1->z + p2->z + p3->z * 4) * (float)(1.0/6.0) ;
}


/***************************************************************************
*
*    print_point()
  *
  *    Print point information.
  *
  ****************************************************************************/
  
  void print_point( point, process_id )
  
  Vertex *point ;
  unsigned process_id;
{
    printf( "\tP(%.2f, %.2f, %.2f)\n", point->x, point->y, point->z ) ;
}


/***************************************************************************
****************************************************************************
*
*    Methods for Rgb object
*
****************************************************************************
****************************************************************************
****************************************************************************
*
*    print_rgb()
  *
  *    Print RGB information.
  *
  ****************************************************************************/
  
  void print_rgb( rgb, process_id )
  
  Rgb *rgb ;
  unsigned process_id;
{
    printf( "\tRGB(%.2f, %.2f, %.2f)\n", rgb->r, rgb->g, rgb->b ) ;
}


/***************************************************************************
****************************************************************************
*
*    Methods for ElementVertex
*
****************************************************************************
****************************************************************************/
/***************************************************************************
*
*    create_elemvertex
*
*    Given Vertex, create and return a new ElemVertex object.
*
****************************************************************************/

ElemVertex *create_elemvertex( p, process_id )
  
  Vertex *p ;
  unsigned process_id;
{
    ElemVertex *ev_new ;
    
    ev_new = get_elemvertex(process_id) ;
    ev_new->p = *p ;
    
    return( ev_new ) ;
}


/***************************************************************************
*
*    get_elemvertex
*
*    Returns an ElementVertex object
*
****************************************************************************/


ElemVertex *get_elemvertex(process_id)
{
    ElemVertex *ev ;
    
    if( sobj_struct[process_id].n_local_free_elemvertex == 0 )
        {
            LOCK(global->free_elemvertex_lock);
            if ( MAX_ELEMVERTICES - global->free_elemvertex
                < N_ELEMVERTEX_ALLOCATE )
                {
                    fprintf( stderr, "Fatal:Ran out of ElemVertex buffer\n" ) ;
                    UNLOCK(global->free_elemvertex_lock);
                    exit(1) ;
                }
            sobj_struct[process_id].n_local_free_elemvertex = N_ELEMVERTEX_ALLOCATE ;
            sobj_struct[process_id].local_free_elemvertex
                = &global->elemvertex_buf[ global->free_elemvertex ] ;
            global->free_elemvertex += N_ELEMVERTEX_ALLOCATE ;
            UNLOCK(global->free_elemvertex_lock);
        }
    
    ev = sobj_struct[process_id].local_free_elemvertex++ ;
    sobj_struct[process_id].n_local_free_elemvertex-- ;
    
    
    /* Initialize contents */
    ev->col.r  = 0.0 ;
    ev->col.g  = 0.0 ;
    ev->col.b  = 0.0 ;
    ev->weight = 0.0 ;
    
    return( ev ) ;
}


/***************************************************************************
*
*    init_elemvertex()
  *
  *    Initialize ElemVertex buffer.
  *    This routine must be called in single process state.
  *
  ****************************************************************************/
  
  
  void init_elemvertex(process_id)
  unsigned process_id;
{
    int ev_cnt ;
    
    /* Initialize global free list */
    LOCKINIT(global->free_elemvertex_lock);
    global->free_elemvertex = 0 ;
    
    /* Allocate locks */
    for( ev_cnt = 0 ; ev_cnt < MAX_ELEMVERTICES ; ev_cnt++ )
        global->elemvertex_buf[ ev_cnt ].ev_lock
            = get_sharedlock( SHARED_LOCK_SEGANY, process_id ) ;
    
    /* Initialize local free list */
    sobj_struct[process_id].n_local_free_elemvertex    = 0 ;
    sobj_struct[process_id].local_free_elemvertex      = 0 ;
}


/***************************************************************************
****************************************************************************
*
*    Methods for Edge
*
****************************************************************************
****************************************************************************/


/***************************************************************************
*
*    foreach_leaf_edge()
  *
  *    For each leaf edges of the binary edge tree, apply the specified
  *    function. Edges are traversed from A to B (i.e., from Pa of the root
                                                  *    to the Pb of the root) if 'reverse' is 0. Otherwise, it is traversed
                                                  *    from B to A.
                                                  *
                                                  ****************************************************************************/
  
  void foreach_leaf_edge( edge, reverse, func, arg1, arg2, process_id )
  
  Edge *edge ;		/* Root edge */
  int reverse ;		/* Reverse traversal  */
  void (*func)() ;		/* Function applied at the leaves */
  void* arg1;
  long  arg2 ;		/* Arguments */
  unsigned process_id;
{
    Edge *first, *second ;
    
    if( edge == 0 )
        return ;
    
    if( (edge->ea == 0) && (edge->eb == 0) )
        func( edge, reverse, arg1, arg2, process_id ) ;
    else
        {
            if( reverse )
                {
                    first = edge->eb ;
                    second = edge->ea ;
                }
            else
                {
                    first = edge->ea ;
                    second = edge->eb ;
                }
            if( first )
                foreach_leaf_edge( first, reverse, func, arg1, arg2, process_id ) ;
            if( second )
                foreach_leaf_edge( second, reverse, func, arg1, arg2, process_id ) ;
        }
}


/***************************************************************************
*
*    create_edge()
  *
  *    Given two ElemVertices V1 and V2, create a new edge (V1,V2)
  *
  ****************************************************************************/
  
  Edge *create_edge( v1, v2, process_id )
  
  ElemVertex *v1, *v2 ;
{
    Edge *enew ;
    
    enew = get_edge(process_id) ;
    enew->pa = v1 ;
    enew->pb = v2 ;
    return( enew ) ;
}


/***************************************************************************
*
*    subdivide_edge()
  *
  *    Create child edges. If they already exist, do nothing.
  *
  ****************************************************************************/
  
  void subdivide_edge( e, a_ratio, process_id )
  
  Edge *e ;		     /* Parent edge */
  float a_ratio ;	     /* ratio*Pa + (1-ratio)*Pb */
  unsigned process_id;
{
    Edge *enew, *e_am ;
    ElemVertex *ev_middle ;
    float b_ratio ;
    
    /* Lock the element before checking the value */
    LOCK(e->edge_lock->lock);
    
    /* Check if the element already has children */
    if( ! _LEAF_EDGE(e) )
        {
            UNLOCK(e->edge_lock->lock);
            return ;
        }
    
    /* Create the subdivision point */
    b_ratio = (float)1.0 - a_ratio ;
    ev_middle = get_elemvertex(process_id) ;
    ev_middle->p.x = a_ratio * e->pa->p.x + b_ratio * e->pb->p.x ;
    ev_middle->p.y = a_ratio * e->pa->p.y + b_ratio * e->pb->p.y ;
    ev_middle->p.z = a_ratio * e->pa->p.z + b_ratio * e->pb->p.z ;
    
    /* (1) Create edge(A-middle) */
    enew = get_edge(process_id) ;
    e_am = enew ;
    enew->pa = e->pa ;
    enew->pb = ev_middle ;
    
    /* (2) Create edge(middle-B) */
    enew = get_edge(process_id) ;
    enew->pa = ev_middle ;
    enew->pb = e->pb ;
    e->eb = enew ;
    
    /* Finally, set e->ea */
    e->ea = e_am ;
    
    /* Unlock the element */
    UNLOCK(e->edge_lock->lock);
}


/***************************************************************************
*
*    get_edge
*
*    Returns an Edge object
*
****************************************************************************/


Edge *get_edge(process_id)
  unsigned process_id;
{
    Edge *edge ;
    
    if( sobj_struct[process_id].n_local_free_edge == 0 )
        {
            LOCK(global->free_edge_lock);
            if ( MAX_EDGES - global->free_edge < N_EDGE_ALLOCATE )
                {
                    fprintf( stderr, "Fatal:Ran out of Edge buffer\n" ) ;
                    UNLOCK(global->free_edge_lock);
                    exit(1) ;
                }
            sobj_struct[process_id].n_local_free_edge = N_EDGE_ALLOCATE ;
            sobj_struct[process_id].local_free_edge
                = &global->edge_buf[ global->free_edge ] ;
            global->free_edge += N_EDGE_ALLOCATE ;
            UNLOCK(global->free_edge_lock);
        }
    
    edge = sobj_struct[process_id].local_free_edge++ ;
    sobj_struct[process_id].n_local_free_edge-- ;
    
    
    /* Initialize contents */
    edge->pa = 0 ;
    edge->pb = 0 ;
    edge->ea = 0 ;
    edge->eb = 0 ;
    
    return( edge ) ;
}


/***************************************************************************
*
*    init_edge()
  *
  *    Initialize Edge buffer.
  *    This routine must be called in single process state.
  *
  ****************************************************************************/
  
  
  void init_edge(process_id)
  unsigned process_id;
{
    int edge_cnt ;
    
    /* Initialize global free list */
    LOCKINIT(global->free_edge_lock);
    global->free_edge = 0 ;
    
    /* Allocate locks */
    for( edge_cnt = 0 ; edge_cnt < MAX_EDGES ; edge_cnt++ )
        global->edge_buf[ edge_cnt ].edge_lock
            = get_sharedlock( SHARED_LOCK_SEG0, process_id ) ;
    
    /* Initialize local free list */
    sobj_struct[process_id].n_local_free_edge    = 0 ;
    sobj_struct[process_id].local_free_edge      = 0 ;
}


/***************************************************************************
****************************************************************************
*
*    Methods for Shared_Lock
*
*    Some machines provide a limited number of lock variables due to hardware
*    constraints etc. This package controls the sharing of this limited number
*    of locks among objects.
*
****************************************************************************
****************************************************************************/
/***************************************************************************
*
*    init_sharedlock()
  *
  *    Initialize shared lock.
  *
  ****************************************************************************/
  
  
  void init_sharedlock(process_id)
  unsigned process_id;
{
    int i ;
    
    for( i = 0 ; i < MAX_SHARED_LOCK ; i++ )
        {
            LOCKINIT(global->sh_lock[i].lock);
        }
    
    sobj_struct[process_id].lock_alloc_counter = 0 ;
}


/***************************************************************************
*
*    get_sharedlock()
  *
  *    Return a shared lock variable. If SHARED_LOCK_SEG[01] is specified,
  *    the lock is selected from the specified segment. If SHARED_LOCK_SEGANY
  *    is specified, the lock is picked up from arbitrary segment.
  *
  ****************************************************************************/
  
  Shared_Lock *get_sharedlock( segment, process_id )
  
  int segment ;
  unsigned process_id;
{
    Shared_Lock *pshl ;
    int effective_lock_ctr ;
    
    /* Compute effective lock allocation counter value */
    switch( segment )
        {
        case SHARED_LOCK_SEG0:
            effective_lock_ctr = sobj_struct[process_id].lock_alloc_counter % SHARED_LOCK_SEG_SIZE ;
            break ;
        case SHARED_LOCK_SEG1:
            effective_lock_ctr = sobj_struct[process_id].lock_alloc_counter % SHARED_LOCK_SEG_SIZE
                + SHARED_LOCK_SEG_SIZE ;
            break ;
        default:
            effective_lock_ctr = sobj_struct[process_id].lock_alloc_counter ;
        }
    
    
    /* Get pointer to the lock */
    pshl = &global->sh_lock[ effective_lock_ctr ] ;
    
    /* Update the lock counter */
    sobj_struct[process_id].lock_alloc_counter++ ;
    if( sobj_struct[process_id].lock_alloc_counter >= MAX_SHARED_LOCK )
        sobj_struct[process_id].lock_alloc_counter = 0 ;
    
    return( pshl ) ;
}